NOTES.PAA[LSP,JRA]28 - www.SailDart.org

perm filename NOTES.PAA[LSP,JRA]28 blob sn#293476 filedate 1977-07-04 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00020 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	.SS(Becoming an Expert,,P120:)
C00015 00003	As you may have discovered, the real difficulty in 
C00032 00004	It %6is%* possible to write a directly recursive reversing function
C00036 00005	.SEC(Applications of LISP,Applications)
C00046 00006	.SS(Examples of LISP Applications,,P255:)
C00053 00007	.SS(Differentiation,differentiation,P41:)
C00065 00008	%1
C00070 00009	.<<abstracting from rep>>
C00082 00010	.SS(Data Bases,,P220:)
C00107 00011	.SS(Algebra of Polynomials,,P264:)
C00119 00012	.GROUP
C00123 00013	.SS(Evaluation of Polynomials,,P2:)
C00127 00014	.<<PROBLEMS ON POLY EVAL >>
C00129 00015	.CENT(More on polynomial evaluation)
C00157 00016	Let's go through a complete evaluation of %2B%* of {yon(P124)}.
C00162 00017	.CENT(Time to take stock)
C00169 00018	.<<AND THE GREAT MOTHERS>>
C00170 00019	.SS(Another Respite)
C00179 00020	.<<PROVING PROPERTIES>>
C00187 ENDMK
C⊗;
.SS(Becoming an Expert,,P120:)
.BEGIN TURN ON "←";
.FP
We have already traced the development of a few LISP algorithms, and we
have given a few  programming hints. It is time to 
reinforce these tentative starts with a more intensive study of the
techniques for writing good LISP programs.
This section will spend a good deal of
time showing different styles of definition, giving hints about how to
write LISP functions, and increasing your familiarity with LISP.
For those of you who are impatiently waiting to see some %6real%* applications
of this programming language, we can only say "be patient".
The next chapter %6will%* develop several non-trivial algorithms, but
what we must do first is improve your skills, even at the risk of
worsening your disposition.

.BEGIN GROUP;
First some terminology is appropriate:
the style of definition which we have been using is called
%2⊗→definition by recursion↔←%*. 
The basic components of such a definition are:
.PT24;
.BEGIN IN@ENT 10,10;
%21.%* A basis case: what to compute as value for the function in
one or more particularly simple cases. A basis case is frequently referred to
as a termination case.
.END
.FP
%2REC%*
.BEGIN INDENT 10,10;
%22.%* A general case: what to compute as value for a func@QS←\X↓OSmK8~∃iQ∀AmCYUKfA←_A←]J↓←dA[=eJAaIKmS←UfAG←5a`↔S∂#'?;~β?9β&CπQβ7+;∂SL¬vrpQ%d,tAQ"u¬F 
↓QKQ3HA ¬↔#∀εA,g]P9t7]v2⊂ #ompare the structure kf a %2REC%*-debinition↓←@→βλβ≠W≠≤εFN}aQ'>OM∧π&F≡@λ
|β⊂0wλ∩Y$g⊃∩U⊗r→s4w4]4ww ob a↓gCh@!gKJ@∀e∪≥λα))β?p∧π←N⎇e¬β⊗p
/@∀WεE⊂x86$Xpz4g[9P7sλ∩Y)"PRU⊗r→s4w4]4ww9H0y2P≤0y:4Xzv0y≠<P:yYs:v⊂~w⊂1g[x:z4[3FE;_v:ryH7s⊂0H3:w1]4ww→2s4w→r⊂7{→y⊂0P≤rz⊂;Z4qt⊂~0yP1→rw⊂2→s4w2Y⊂1<P_wεE∩L$g"∩J⊗r2s~w4z4[w↔⊂εB#7y⊂→|0vx≠2V⊂0\yzvrH:40zλ;rP4_{2P2→s4w2Y⊂0P9Yz⊂∩r⊂RU⊂:\tw3P	Y$g"	U⊂⊂:~2w⊂0H:<x4XpvεE_v3wy~z46P→7y⊂1[vx:z~w3P0HεE3:[1z4w[⊂⊂∩r→∩U⊂⊂≠{2y⊂	r RUλ;wzv→⊂4w;≠v;2P≥;wP8_y:9]λ34y9]⊗⊂εE_w⊂4w→4qpz~ww⊂7Y⊂47{H:7P1[vx:z→FE∩r→∩U⊂7[⊂:42H10yrH27vpZw⊂7sλ∩r RJ⊗⊂0w→⊂9rq[w2⊗⊂→t{2wλ;0v:YyP37\⊂9wvYP2v2[rw:9CE7s⊂	r RUλ9p|P	r0RZRXV⊃K↔↔⊗∩Y0RZ7	XVεE≥yrP∩L$g"∩J⊂:7P→rw2y_z2P0H72{P→v2vr[:⊂∩r_RX]P≥42w⊂≤x2qtY<P:4→P;0v≥pP7sλ∩r3∀_TRUεB0yP0H3:w1]4ww⊂≠q⊂:4→P5w7]w⊂⊂;_v:ryH5s⊂∩Y3∀0RM_RU∀IXV⊃W↔⊗⊃P	p∧f(a%4n%*)%1.
That is Exactly the structure kf %2REC%*.

.P1⊃9:~∀9¬∂∪8Aπ%∨U v~∃!KeJAαK@~ε≥mw&F↑ λ≡≥≤Z,.αz2P≠pε %2IH
λJ([AKM%]SiSα{;Mi¬≠WCC⎇≠∃β←*β#π[*β∪↔≠Ns↔⊃βλ∧hW<X
∧∧9⊂!%$≥<p∀[3P∩Y∩dεD%*, and se @]SgPAQ↑Aae=mJAi!ChAB↓GKei¬S\AaI←aKeQr@~∀∀e JT↓Q←YILAMOdαβ↔[↔↔Iβ↔3.k↔;Q∧¬v $	9⊂$UKH∃lT≠Y1,D≠{[∂∀≤z≠nt≥~_.G@εE↔⊂"cdgλ$g""S*⊂_X_X≥FB↔(*→
εA∩YU∩U⊂λ∩Y(∩J⊂47v→9P37\⊂2{2\<P2v→vrw:λ7s⊂:~2P10\rP27[ptw⊂≠s⊂∩r⊂RU↔εB↔"g"βE↔#(βE∩Y(∀#∩UεB↔!"cRg⊂$g⊃"g*⊂X⊗_X∞FE∩Y↔∩U⊂∃ytw3H:42FB:2qt≠4xzbH;rP2[0q7y_z2r⊂~w⊂22Y4w4w→P⊂:4→P3:w_z4wwλ∩r3∩J⊂0q7]2V⊂4Y⊂;rFB1pw⊂≤t7{P≥40z⊂	Y(∩Uλ47v2≤P37yλ:42P≠2{P2[2vrw≥⊂82y~0x9P≤2v<t[3P7wλ897wY9FE7Y⊂∩Y(	U⊂37\⊂9zqrv2vYw:9Vλ:42wλ;rP9Z7zv2λ40{"H0P1w[;4w1Zw3P0\3zvr[:⊂:4_zεE∩L(∩U⊂~7v29H7{2yλ∩[0v≠∩U⊂7Y⊂∩r IU↔εE"g"εB↔(*→
εE↔"S"εE↔⊃(εE*~4yP8≤7ws⊂≥2qt7~xzrP~yP0P→rw2i_v4⎇0]4ww⊂≠s⊂0P_wvvw[⊂:2qZ74xzYFE37\⊂897]4w3@≤97x2\:4ryH7s⊂:~2P4w≥2sry≤W⊂$wλ:40zλ1ww:→|:⊂4]⊂4yP_pv62YεE6p]42vp]4qpvλ4w2:Xz4wwεEεE∃rP0y→P9rrZw3P0[⊂4w:→y2yz~w3P8_y0v6→v⊂12];rrwλ4w2:Xz4{2H22s4[4z4w[9FE7Y⊂9rz≤V⊂92Xzy9t]2P22Y4w4z~ww9P≠s⊂3:[1z4w[9V⊂0[2⊂89≠ws9P_<P4w→:qz4[w↔εE⊂yP;rH897qYrr⊗⊂≥rP;t[6⊂2|≤67tzλ;0y4[zyP0\x2qz≤P7s⊂≥42yrH⊂4w:→y92v_z4ww≤t4x9KεE$7]r{2yλ7zy⊂≥0yuP_z⊂40[2⊂4yH6wy2H6zw2_w2]⊂≥7P22]2v7xλ30qt[4z<P_zεE0\86<t[3P∩Y∀"aRUλ:7P2→s4w2H3:w1]4ww9H7{2yλ:42P	Y$g"	U⊗r7[ptw9HεE7sλ9|vq≠v4qP→|892\ytww≤V⊂∩r∀RU⊗⊂λ0w2⊂≠s⊂9r\zrw1YyV⊂∩Y)rxRJ↔εEεB#4y9]⊂62z	yP;2\4s<P≥40z≥42P3≥w1z4[w9P;YP40{→FE1w[9z9:Xz2r⊂≤wP30\⊂27P~w22rY⊂9pz~ys<P	Y)"aIU↔εE∀2qpv≠⊂7zyλ2|0v\62P7Y⊂∩Yr\zpv∩J⊂7w⊂≡|ww∀∀_T␈↔λεE42H10yt\P1pyYP4w;≠v;2yH0P1p[1zv0]4ww on members kf %d<atom>%*;
there we rely on %3eq%* to distinguish betweef distinct atoms.
The quesTion od∧AKcUCYSidAM←dαβS←=εs?97∂#?7'~αM7↔GβKMβ>EβK.≠πOQεMβ∧hSGW↔∨#'?9ε{⊃β↔∂+π3''Iβ≠?⊂βS#↔M⊃↓∃O≡I∃+~βπ;⊃α)O∂∪⊂∧RW~dλ'/"∞Mε∂"∞Mvz`Q-↔~π∞-wε/$∞6Nv<Tπ&FT6}w>N'.∨L\Bε}-,V∨"
≡2h-\⊗w.l≤7'/,\Bε↔∀∧S≡≡⎇n2*RD⊗v"∧V6≡∂$U"ε∞lDα+≡<N"*R
|bπ&≡Bε}-,V∨ Q.6.f\>Bπ&Tε≡}↑
vv.nN2ph!Q%≡N]≥F∂∩
.W∨&≤m⊗≡∂M≥vrεm}"α+=LVv?M∧RRε⎇dπ←N⎇e¬β↔¬↔rε<≥bε⊗TvO6]e`hUMW⊗*∞Mε*εM⎇V∞Nd
↔
α\J6/
U%b¬&Tε⊗∂<Tε&}\≥⊗rε≡4π&FTVoπO∀π≡∂≡XVv≡UDε∞vAQ"+≡L]f?&∧U"εO4F.6≥lV"πMtε>OlTα+≠∧U"εNd
FF∂D6∂≡U`¬&FTv.v↑,⊗bε<≡6*ε≥dπ&FQQ'⊗.>Z'=8πw comes from
the %2IND%*-definitionob asaqu@∃]GJ,¬≥WiJQws←8Q bbβ!'y%π##πQ¬;∃β∪N#9∨Qε;'[∀hSπ9β-CC3'≡KQ↓∃∀J:"U%V&.m≥fO&≥⎇bbε.X
∧∞X=~↑H_(∞<=λ≠ld⊂SQD<=8.M;{\ea"U~T≤Y8,L<H∀m
⎇;→∧∞⎇<≤
O(≥~T→>≤
M8z=∧→9Z-m=~;meWkC!(z=Y-d_(≤l↑=9;L<(	,N4*Kλ∞|(≠8,L(_(
l=h≤l↑=9;L<(_↑$9→~-lh_(∞<<=9-ly(→-L;9;NA"]≠d∞~→(n[{]∧
yH	&.i*KDλ9x:-d≥~→${{<∞↑_=~-⎇H≠yD∧,{→-l⎇~	%$≤_<L≥≠→;∞1"]~
≡h_{mn⎇≤],>~;{ED≤x>-≥Yh≥
=λ≥
(≠→-l⎇~λ
|H≥~
≡h≠Y.t≤y<.\;Xy$
<c"M⎇Y(≠-}Y(≥
;H≥
(≠→-l⎇~λ
|H≥~T≤y<.\;Xy$∧,\i%%C"C!([|H∀≠;|LT≥≤X,M=~;ml;λλ←_;<
L(_{mnz9→.$≥~→$X8⎇
}Z8;∧];XnM;{K∧
H+C!%T∃FA"KSIA"I,F∃I*Hd:~→(n;X⎇
≥{H~.4→→9M≥Y9λm|H≠M⎇K;Y,|=~=LT~;]\y<\ea"KSIA"I,F%I*Hd:~→(∞l;≥9$
yH≥
(→]-l⎇~;md→[|Dελ~<dε+C"EiSβ"DVLi*Edhs⎇
<]z.<(≥~T≥X;∞\(≠yD
H(~.4≠H≥
≥9<h∞M→(≥L≥≥9(
|H
≠EV*(+AQKT∃ε&β"KHzSu4π1"R=∧∞z≠⎇-Lλ≠[nt_Y(=→8<D
≠⎇h∞Mh≥|M≡→(_$	∩4t∧∞≤[yn,;(→M}H≥~T→X8nM|Z8-D→];L>~;{G!"C"EhQ1r)d⊂q3JH4R5π:q3⊃(:λnaQKTFπC"KH)v⊂#!+yX8nK{W(πG(⊗y.≠{NlTε('4	9=∧UHε(∞M;9<k=NyX,>⊗|⎇,&6{W+[7(¬@∀,⎇~-\<i,$
<hβ!,(∪∩*:λ→]-l⎇~;mdλ≥z
≤zλ≤↑Y[|M↑h≠=-N~<≠
≤x=~-⎇Kλ_-lβ"H∧V|⎇8F∀,(≤n\]≤X,>≤h	&6),(n[{(
≡≤h_.,⎇;9-nWc!%PSvλ!"KQ)hβ"KH~⊂4U↓QKQT↓QU~→$
;<≠
≤x=~-⎇H~<d∞~_=∧
=λ~.4λ→8.=9<H∞Mh_{m↑≥=→$¬≠K,%∀(≥~≥C"]
t_{{.∞=→(
d+H⊂N↑λ≥~≡λ≥≠mt~<h
≥H_8l=|Yλ∞⎇=~λ
}<H_m⎇\⎇≤N\⎇~;md≠yH↓Q]~→$
;]→,|<\h∞↑z;Yd∞~→(∞>8xy.>{|Hn;X⎇
≥{KC!!"U~↑y(→/;<≠↑h_<LT≥≡<
≤x;λ
|H∪∩*:	|h∞,8⎇<N==Y(L9Z;M≡~;{N5C"U
(_[lO(≠yD∞~→(L9Z;M≡~;{D
<h_${{Y
≡~;{L≥λ→>∞∞Y<|m≥{Nh∞M→(→M≡\⎇λl=c"L.X;Xm<h~-n[{≥LTλ≤|\z8;∧x<y.5λ_x-M→9λ∧VEF=↑[:;L≡~;{D{{Y
≡~;{N2wi*Ea"U~]Hλ≥
(≤Y-\:;Y↑H≠yD∞~→(={Y~.M;{X-D_{⎇L↑\h≥
(→y-l<X;∧x<y%U(≥z≡λ≥≠aQY≠h
≤H≥~T_<Yn]9;]∧∞≠h≥
(→]-l⎇~;md~<h
m⎇λ≠ml(≠yD∞~→(∞>→8z,≥λ_x.<<kC!!"S[nM8y(∞M_=λ∧VyX8nD*H~.4_(≤≡]~8-D→];L>~;{ED→→9M≥Y9λ
⎇[≡(m|H≠M⎇K;Y,|=~=LQ"Z;NL9y<N5Hβ"J⎇→;H∞}Z=~-lh≠|D∞Y89
≥Yh∪	~tλ→\Z;Z.M;{\d∞_>(∞<]~,>;_<D=≥→-n~;{D∞≠h≥
#"Q
⎇8:;D
yH→\Z;Z.M;{H≥Yλ≥
(≤X-ly(≠ld≥X;∞\<h≤∞-y≥0l\Hβ!*~→(m{≠≠n⎇;Yh|;Y<L≥λ~~-n≤h≤m
⎇;→∧;≤{dY(≥.<9];π!"KT
FMβ"EiS∞c!$,L!%%Hhr.4≥~→$;→{n-=~≠$∞≠h_LTλ_(	I4tλn;X⎇
≥{H≠n∧≤≤Y,M8x=Wh∃~
≡h~;Lm|[8.M;{H<;H_LT≥<q,D≥≠c!,≠⎇8ML+8z\zh≥.<<h≠lDλ≥~T→→9M≥Z=~-⎇KH⊃
⎇I⎇∞↑y(_$∞≤Y9
≤x=→$∞z→<LT_(β!*k9>∞∞K=X-N99λn;X⎇
≥{H~.4→>≤\⎇→9π4_;Y∧≠{InD≥<q$;H∀e\>≤≤E↑X;≥,\λ→]-l⎇~;ma"]z↑Y(_$
~<⎇¬↑X;≥,T~<h←≤→8nL9C!%SSβ!$,LI%%Hhp.,(≥~↑Y(λ∞,<⎇≤M≤⎇~3mnh≠{D∞~→(≡Y⎇;,]]λ≤
}z=~-⎇\oh↓QQ[|D>_;.
→+λ
↑<⎇λ∞={9(
|H≥~T_<Yn]9;]∞4_Y(∞N]=~∧∞X;≥,↑oh∀m≥:;_.!"Xsmnz<⎇]X}(=→8zm≥Yh_.4~;H∧VL)*Dx;@,(→≠ml(≥z.Mλ≥~
≡h~;Lm|[8.M;{KAQKSS↓QI,LdUKHhh≡Y(≥
(≥→.-:;X.M;{@={Y~.M;{\d{{<≡~8[T≥z=
∧≥~→$∞Y<⎇∞-8⎇~-⎇\c"M⎇H≥~T_<Yn]9;]∞7hλ∩,d~=λ
≡h_(∞,8⎇<N≥;{H
⎇H≠~.>≤kλ=→8zd[|H∞M→(→-↑≥≡#!-~<⎇π4~9H
≡λ~<d(≤Y,><\r-⎇H≠yD<XZ.NX<↑$
k9>∞∞\kλ∞M→;H=→8zd[|H∞M→#"L≡≤→8.,;Xy$
yH_-d_=≠mUC"KIiβ"I&&	*KD4uz→-l=Y<D(→]-l⎇~;md_x;
D~<h
\9→(∞⎇=~~-d≥~→$→9Z-m=~;meλ_<LT_;≠↓Q]~→$∞Y<⎇∞-8⎇~-⎇\h≠md≥~_.D→];L>~;{D∞x=~.<Z99πq"KSIA"I,FT*KHd8≠{InD≥≤↑$∞≠h→
t≥≠{d
=8z¬d∃≤↑$∞≠h_LT≠_>O∃H∃~↑Y(~.4≥<⎇,≥≠≡(∀≥Y<O∀≤z;.
→#"NL<[:-l=~;md_x<lUHβ"I≤H≥~T≥→<M];X=
≥{H_l≡hing wrong with your
conception of the program.
If the general case looks messy, then write some  subfunctions
to perform the brunt of the calculation. 
.PT24
.FP
Apply the  suggestions when writing any subfunction. When you are
finished, no function will do very much, but the net effect of all the
functions acting in concert is a solution to your problem. That is
part of the mystique of recursive programming.


As you may have discovered, the real difficultq in 
programming is writing  your own programs. But who says programming
is easy? LISP atleast makes some of your decisions easy. Itc
constructs are particularly frugal. So far there is only %6one%* way to write
a non-trivial algorithm in LISP: use recursion. The structure of the program
flows like that of aninductive argument.↓
S]HαβS#∃¬∪'∨# ∧εNvN\7&N⎇dεGO
zFF/=~0hV≥lBπ&TεNvN\7&OlTππ⊗⎇xbεO4V∂∨↔4ε6NlDπ&FT
&N>∞Dπ∨'.\7'∂,Tε}r∞⎇εN≡∧∞Fzπ,\7/∩↓Q&∞vD
&.∨↑.6O6T∞π⊗↑},⊗nn≥lrεO4λV∂∨∃`∧O"}4ε.∂=_	.∧≥≠h,9z;D∞z=~∧∞9X<O∀→];L>~;{N↔c"U
;H∃
<Y)n∀λ≠[d∞=94nM;{H≤[⎇=∧∞z~8m∧_<Yn]9;]∧↓"Z<d∞≠h_LT→→0m⎇<≠p→Yr↔⊂*~2P7g≠<P22Xtyt`/n 
iq hoW to terminate the recurs@%←\\@↓∪@→β&C∃βπ⊗;W7↔w!β'Mε9αMn+cCHhS←*∞O↔εN<≥FgJ∞LW⊗N≥l↔&*
ybπ&Tε}≡>↑'⊗.l<Rε↑d⊗rε≡Mvj@H∩1D∞~→(≡Y⎇;,]]λ∩.P0FE≠4yz, then p	Ke5S]Ci∀A←\@∀fPFR∀T\A∪_AiQJ↓CeOk5K]hAαKEβ¬εsW7/⊃βS#.qβC↔⊗k';π&)β?9πS↔K=ph(4)t:J>VβX4*∂}sG'∪/⊃β¬β≡c'∨#&ceβ7␈∪∃β∂}kC3'≡S↔⊃εK'SFk↔S'≡1β↔F7C3*aβS#*4(XL3'?v∂∂%π≠↔GW.s∂∀↑{Q↓A1≠	1
Eb→I1↓~a
U1≠A1
9rq
9α&C'Mβ≤∧W∂.]l6*ε<≥bε⊗QQ&≡F≡,⊗∨&↑-↔V.D'JπMRε6⎇H
}z;Yd∞Y8⎇..Y;XlT≤Y;≡~;{G!"C"EhQ1r)D⊂q3JH4R5π1"KPI[⊂#"Ehβi'jTε@
←f(0! = 0
←f(1) = 1
←f(n) = f(n-1)+d(n-2);
.BOXB
.APART
.END
.APART

.@∂%∨U ~*&C∃βS⊗;O3∂#'?9π#=β¬∧b&NAε3W;∂&K?9βM→β↔π∨Ih4(hQ:
⊗<J9αR∩&QIC	Y1IBInN⊗d*∞@"ε74=∀zZβXh%h$`;⊂#"KLZ8Vmk(∂∂+Ky<6mgl↔ ⊂εP_≥FB..⊂2\mw≥XWPP_NFE..λ∩rz∩J⊂P(≠:yms~q-yzX_mw.W]s4q⊗yzq_Vyzq_Vw.nnWnFE↔⊂'l!εB↔"g"βEεE;Z2y2P	Yx6:\RU⊂4\P0P9→x92yYw:0z~ww⊂7Y⊂:42H6pz4→vpz4Xpv⊂3≥w1z4[w⊗⊂∩LURU↔βE↔ h⊂i*εEβE P3→{P0r→4z4w[0v⊂8≠tw:9H1pw⊂_2P6pY2P42\2W⊂'≠z4qrH:40zλ0w⊂2]0v:p]4wwεB9qt2[rP6p↑P4vx≠<P6p[<P2:\64qp]2P1w[x:z0]4ww9K⊂⊂#7\⊂2|0[x62VβE1wv\:z0z~ww⊂7Y⊂∩Ys~q-ZnIU⊂92\zty2\P:42H1wvx≥z0z4[w⊂7cλ∩Ys4X-Z.BJ⊂0w2λ∩Ys4X-Yn@%*.
But within the Calculation of %3fib[4X
JT↓oB@A¬OCS\↓GCYGUYCiJJgMS	6g:J(X~∃Kβ#
9↓∧KQβ←␈+3⊃β⊗)β;'≤∧RεNd∞v*ε=}Vf"∞,W∨'.\7'<Y(∞M→(→\Z;Z.M;{H
|H≥~T→];L>~;{AQI,p∪~q∩U⊂≥7P9z≠x⊂:4~yP2|≥90P1[vx:z_z4ww¬`w⊂_v:2y≠0z4{→P9wv≥z4wwβE4yP≥7P9z\86<P_P24s→2y2w≥⊂2{0[:pz4[w⊂9qZ2vrP≥t4qtλ6tst≥⊂12P_q62P≥5P92[rrq2\εE89→{4wz\v<P1Xv1zv_z2r≤2yzv≥9W⊃K↔-cwzλ[Z.o/W⊂)Zw1rP≥pP∩[→7RU⊂≥tyt≥7P9:[εE89≠sy0v\P7w⊂_P6pqZ4w2P≥rP9t≠zv2⊂→t{2P≤wvrP_z:2w≥4ww⊂≥7P2s→4qtr[1|KQ7y⊂εB:47yYP92pY2y9P≥tz4⊂≤wvrP≤97sy_vvtw→P2|8→y4rw_rV⊂εB:42P≤wv:z~ww⊂6X|P0x≤2py⊂λ2py|N⊂0yyZsw⊂:~2FE8_y:4p[⊂1w`-putations tk temporary variables.  The problem here is that
our current subset of LISP doesn't contain assignment.←.

.GROUP;
We will define another function, called %3fib%9'%1, on three variables %3x%*,
%3y%*, and %3n%*. The variables, %3x%* and %3y%*, will be usEd to carry
the partial Computations. COnsider:

.BEGIN TABIT2(17,33);SELECT 3;CENTERIT;
.GROUP
.BOXA
←fib%41%*[n] <= fib%9'%*[n;0;1]

%1where:%3\fib%9'%*[n;x;y] <=\[eq[n;0] → x;
\\ %et%* → fib%9'%*[sub1[n];plus[x;y];x]]
.BOXB
.APART
.END
.APART
.FP
This example is complicated enough to warrant 
closer examination. The initial call,
%3fib%41%*[n]%1, has the effect of calling %3fib%9'%1 with %3x%* initialized to
%30%* and with %3y%* initialized to %31%*. The calls on %3fib%9'%1 within the body
of the defini@QS←\X↓gCrAQQJAR∀qiPJ(AgkG AeKGUegSm∀AGCY0XAQCLAiQJ↓KMMK
h~∃←α1βOπ4¬⊗v:∞Mε*ε∀Wπ&BU$∧6N-⎇f∞≡=∀εw.\,W∩ε≥dα+∨∧U"ε∞lDπ&FT	∩k
W∞7"*$
⊗rαV?∩*RaQ"t≥)zUβXQ(f␈∩←ε∞o
HSPh!Q"t∀Xy∀r¬H_$M#%ε#*c6e∪]≤YHT≥λnhzSu4π1"KPI[⊂#"KLZ8I&F)*VfK(↔∂$Z8I'∀i*VfGl∞`_WFE..∂P34q	\SRU⊗Y]X]L.FE.↔≡P34X∩\SRJ-Y≥XNXnFE↔.≡P3~q∩\SIU-X]L≥XnFB..≡P→4q∩\IRU-X∞Y]Y.CE..≡H→FE↔⊂'l!εB↔"g"βE↔ h⊂i*εE!(εE⊃:w1z~ww9P≠4urP	Ys4q	\SRXK⊂:ybY⊂:7P~2v8⊂	Ys4q	Z_RXK⊂0y2H1pv6→r⊂⊃4→v8⊃s≥w1z4[w9QεB7y⊂∩Lpz↑4v4p\<Qs:[1z4w[oyRL]P;0\4pq6→yP64ZrP∩Y↑∩XP0[2⊂∩Y↑RXP4[⊂∩Ys~q∩\SIXFE0\2P1p[62r⊂	YpXqzvz[0z7y≤KoRXHT/-Swwy⊃MZ.o∀K⊂εE9Zw1rP≥42|P_y2P:\rr⊂:≠P0qq]vzv0]2P:4→P80y≥4pv⊂_wvx:]0z4w[9WεE∃42P:→qt74\zrP7Y⊂:yt[3P0z↑4v4p\<P3:[1z4w[9P0w→⊂0qq]vzv0]7y9P_pw⊂εB0v9wH12P0\864rY⊂:7P≥42FE→0qz7\4pv⊂→|0vx≠2W⊂+Z2w⊂;~r{rrλ1wvx≥z0z4[w0v6≡V⊂:4→P92y]v:4w→P22s~w4z4[w⊂εE≥tv6⊂_2P6w\2P2s→4qtr[:⊗⊂:~7zstβE:42H3ptwλ4w⊂2Y34qtYw1|P~yP77]⊂0yP_x80y→w:⊂⊂_yP:4_z⊂4wλ:42P⊃4q7w_qqtFB2|0v\62Pj42P	Ys4q	Z_RXH2|0v\62P4[x97{→yP2s→4qtr[1|P6[yz6<HεE1<H1pv1]v0z4[3P32]ry⊂4[:2y6Yr4pz→P92y]v:9WβE*42H3ptwλ4w⊂:~2P∩YY0qz∩M_RXP→|0vx≠2P4yH4w;7[;2r⊂≥tz4⊂≥42P6Xqt4w→y<FE≠2qry\py<P≥7P0q]:pv6≡P2|2Xzz2P≥42P8≤7sy0[]⊂:4→P9:wz4vrCE2w;~y7w6Yw:⊗⊂~s⊂<w]P;tyZ↔⊂+rH;tv6λ24yq]yyP:~4yP;Z2w⊂;YP:0v~P0q7]zεE4[x62vYw:0z~ww⊂7Y⊂&$iT⊂4w⊂≡|ww9YqT(_L≠T␈↔λ*42P≥t7v2H8zry]4ww⊂≠s≥⊂⊃≥t0z⊂~yFE2Y34qtYw:∨Qλ4yP7\2w⊂:≠P24yXzyyt[w↔/WβE↔#i∪jh≥FB↔#(εB*4:yNεEεE!"cdS⊂* a∩j_T_L∀]ibS"aj⊂]ci'Uh≥abS*"i$U≥FE↔∀→_]εB↔!'l⊂FE/s_qz∩ZRU-w↔P≡≡P→0qz∩NSRU-[≥Xn]CEεE∩L{t2y→]∩YoY0qz∩NSRU-[≥|.P∂≡P-r\mw≥X↔PP<∞P∩rz	U⊂P→0qz∩NSRU-\zq_m[.]z4[pymw∞|.nnCE↔17↑1εE↔⊂h i*βE↔"g⊃εA↔ T i*≥CE↔#(βE$z⊂_x82p\9P⊂:~0z⊂:~2P80Zy9P∩Ls0qz⊂30q]∩Z_RLP0w2βE∩Ys~q⊗⊂3~q∩Z_IXP0y→P2xzZ{0v2[:↔⊂(→y40x≤P;rP≤t7zv→⊂897]2P:4_z⊂:4~yP4yH9wWεB+rP8≤2yrw≥2r⊂:~2P⊂1\:qtp[⊂4r2XyP37\⊂:42H897wY⊂4w⊂≥42P2~yqzy\tww⊂≠w⊂=|[w∀(_L\T␈εB1ww1Yy74w→P∩Y$S"∩U⊗λ∩Y)"PRU⊂0[2⊂∩Y∀)#∩UεE+rH9t0v≠⊂2|0[tw2P≥42P8]ryz4[w⊂7sλ897wY9P7sλ2xzt]0v2w_rP4wλ=|ww≤yT(_MT␈↔εBεE↔#T'jh≥CE z|~v4py≡P3:w_z4ww≤P0y2H0v9wH⊂⊂0x≤64qpX62P:≠P&$iT⊂3:w_z4ww≤FE22Y4w2rλ7{2yλ)Vr|≤99]εBεE↔!⊃cdg⊂⊂bg*"T$j≥iQf"ajλ→]sy≠zx≥FB↔(_\NεE↔!∪l FE↔v2w3]4-w.H≡≡P-[:v6-[,PP≥P∩r]∩U⊂H0r2_Vv2w3]4-y2\z-w.WnnPpr2_V|.P≡∂P<∃XWFE↔(∃_\εE↔v2w3]4∩Z_IU-w.H≡≡P6→w3z4	\SRU⊗w≥X.CE↔(*εE∩X]t2y2N∩Yov→w3z4	\SRU⊗w≥|.H≡≡P-[:v6-[,PP≡≥P∩r]∩U⊂H62w3]4∩\SIU-y2\z-w.Npr2_V|.nnCE∩Xp[2⊂0sXtw⊂4]⊂0x8→py9P≥40z⊂	Yv2w→z4∩XH4yP2\zt{0[2w:⊂≥7P∩Y[2w3z~∩Z_RLWεE↔_7|1εB↔ h T*εE↔⊃g"εE h i∃εEεE∀wP30\⊂7zyλ2|0v\62yP~0{2P→tz42\⊂12r[⊂7:vYy4qp[⊂7y⊂~0{2P_2rw⊂≤92r4Xpz2yKεE(9→r4qp]2yP7[6<P9→xzty→P:90]2y9t[3P2|~yz4w→P)Vr↑899]H1ry:_tw6<H⊂;rP≥tv6εB;pw:λ:7P;\4z2P_v3wy~z46yH;t4qZ⊂1:t[2⊂72]P)Vr↑899Wλ⊂!ww≤tr2yλ:42P≤97q6→vFE7Y⊂;y4]4w3P_P&$iT⊂0v3[y4z4≠P:7Pλ92{2\9rP0H64yzλ∩Y|∩J↔⊂*4→y2P4\P0P9Zvx62H4w37\6pvεB1wvx≥z0z4[w≥⊂:_urP2[2vrw≥9P39≠vP:4→P397[:⊂7sλ∩Y|∩J⊂⊂0w→⊂8:zλ:42vCE7w:≠P:42H397w≥⊂7s⊂_P72{H64yzλ∩Y|RJ↔⊂$w~z4pv≠<V⊂∩L|RU⊂≤t7zv→⊂12Pλ∩YT⊃JRU⊂0[2εE:~en %3x%* is empty. 
.GROUP;
For example, reversAl of the list %3(A B C D)%1 would ProduCe the sequence:
¬
.BEGIN SELECP 3; TABIT2(32,49);
.boxa
\x\p∩~)8QαAλAεAλ%8P@R4∃8Q∧↓αAλSpQαR~)8QεA⊂S8Q∧↓αR4Ua"⊃εbB
α	∧	$4*bA↓&qD!α
α⊂α¬$∀Rr⊗:⊂hQ:
>D⊂4):
αεJPhP4*←FQβ≠|c3?←~β'M↓α)OK↔4+CO∃*Q1β←F+K∃β>)βWO*β¬βO.⊃7≠Wv≠S'?ph)∃O⊗+Y∃e:)EβSzβ∪=β&C∃β#∂∪⊃β←␈∪%βπv!βC↔⊗3?K5¬##∃βLs'S'∞c'kπ&K?9β>KS!hSS#∃π≠↔∂?v!βπK?+7↔;"βS=↓+≠K↔Y+I≥∃Eph(4)t∩⊗≡εrα∞⊗:$*J&Q]~⊗2⊗≥!↓Mn=∩>VAXh):AI9h4)t∩0≥D⊃Q%␈⊗↑hWπ≡[?¬jβGTπ⊗/dW∩:*+?βZB¬≠PhRj
C⊂H+z&/2W∀r*U?π7MjπGR¬↑n]Fe←T↓Jπ↔4α./DU"↓J∞,W2+∀tRU←,↑7%←S6≡}l<↔%↑m≡'∨%?SOM[[PhRh)uD⊂β"KH~⊂4U↓QKQ3HA ¬εE(_[≥βE↔#(βE*44\P∩Yi→{2y9YRU⊂3≥w1z4[w⊂1:Zv29P≥x⊂:4→P72kH64yzλεE1<H⊂∩Yq[w1pz	U⊗tw→FE:4→P2v2[rw:9H7w:7H:42P≤rqww→⊂0y3]vrw:λ7s⊂∩Ly2{∩NSRU∩LU⊂)t[1rP∩L|RU⊂≥pyP4[4z4p[4⎇2rβE:7P	YT⊃TIU⊂;rH0y2P_yyzy→r⊂:4_z⊂:4→P92y]v:4w→P1ww≤z9:q]⊂;tv≠⊂12P_P64y]↔εE+YP;tv≠εE9rYP0P⊃→4y2q]⊃⊂22Y4w4z~ww⊂7Y⊂:42H92{2\9tw3H3:w1]4ww⊂~w⊂0P≠wvrw≥↔εEεBεE!w[9z9:Xz4wwλ4yP:\zpv6≡P77zλ8ztz→P9wP≤z90tYt:37\;py2⊂)zx≤7yrP≥rP92\zty2HεE⊂0H&$ihλ3:w1]4ww⊂≠0vrrλRYXx82w→∩UoH7s⊂:≥wP64\z⊂0y→zvrw≥9V⊂∩L|∩U⊂_w2⊂∩L|RU⊗βE;t4Xt⊂4yH:7P9→z:y7λ0P72]P64y]⊂;t4Xt⊂40\P∩Y|	U⊂0x≤2w22Y⊂7w:≠P:42H397w≥⊂7s⊂	Y|RUεE#7\⊂2|0[x62]βEεE↔⊂"cdgλ!bg*⊃i$j≥Tbf"aU⊂→]P⊃i'jh∞FE↔"T]FE0\82w2⊗T P!λ"∀]T⊂P"TnH≡P∀ H!⊂"⊂⊂P"TFB↔"hXJ_ZT]CE.0x≤2w2-P]T!⊂⊂TnP∩LP≡P∩Na∩XP≤tw1rH∩Y`RLP4yP≠7z⊂0H64yzεE.∩Lpx82[2-T H!⊂!TNT⊂∀nH≡P0x≤2w2-J⊂∀]T⊂P!⊂!JnP≡P
 P!⊂⊂TFE↔⊃g"εE h i∃εE↔"S"εE↔⊃(εE∩Lpx8"[2∩U⊂~yP0P≤0y:4Xv⊂3:[1z4w[≥P4zλ9t7z[2⊂12H22s$[2r⊂1≡P92q]y9tw[⊗εE1≥z⊂92Xzy9`)on oN which argument?  IF either argument is %3(#)%*
Then the value given by %3append%* iq the other argument. 
The nexpλAg%[aYKMhAGCMJASf↓BA←]∀[KYK5K]h~)YSghβYβ'→ε+cπ∂&ceβ?v)β/→α)Oa∃Rβ?I↓+≠e∃)εKMβ¬¬≠';∨d+S?9εC?]β&{↔Mβ&CπQβF+3Aβ/_4+∪O≠∂?[/⊃βS#*βK↔∂/∪K↔;≡)βK↔fS'?rβ≠?IεCC↔v#';≥zα'Qβ&{↔O9?!β#↔g↓β7W≡Aβ'→α)Oe∃Ph+'Mε	βO'v;3↔S}qmβ/!β'→α)Oa∃Rβ'Mβ
βO';>c↔S?raβS#.q↓∃O∂βC↔;"))β∂␈+3⊃β>K[∃hhQ:BQ@4*⎇+≠∂?;≡Ro≠O∪ORoEiofu*QβπMπ∪↔OWg!84)uαQE`hQ:~@hRO=β⊗+∂WK≡K?9β}q↓∃OB))β'~β3'/.ce9α&C∃β∪.3';'&K?9βv{]β≠}c3?←~p4(4RrAIIPh):
⎇B∧4*z)OπCε+;∩oC[fu↓ciαo;.c2objeβeZ↓↔↔Q*Qeβ≡{;∂π%[≠'K∨"obu↑CC↔v"oK↔∨"obu←Jvvur)D4)t∩>bλhQ:~@hR;?SN≠∃βSFQβSF)β∂?w≠SKW∨#'?9ε{→βSF)βK↔∨+3QβO→β¬β⊗KQβ7␈∪∃β?↔≠∂WK*βS#πph+S#∂!β';6{3[↔"β'9↓+≠K↔[/∪O∃∃RqαS#*β∂?;∨#KW∂&K?9βFMβSz↓←πO!	βWw#'04W;∃β#∂3∃βO.+9βSF)β↔;"β?→β&C∃β3O≠Q↓∃∨A∃)9∧3?Iβ/Cπ7Cf)h4(hQ:
⊗<J9↓α≤*2⊗∞"↓Mn≡∀zVAlhQ;SW∀qα>9α∩q	m∧r>~&damαR∩M↓Ec⊃M1M∩aMe1#1l4)tZJ-mh):
⎇B∧4*fCC↔v"m"¬∧⊃α
%ZB⊃α∃∧1&uαciβ∂?v≠πRn[πCC.s∩m"∩α
%mD!α∃α2Jvt∀Ubquβ≡{;∂π%Z¬o∂}s∂πR\⊃oπC∧+;∩mD→%m""α∃α→MjvtQ+Ecj=vv≡≡K5d1Q%eeL=vv≡≡K5d∪1Q%eeKL6}v<≡E]d71PUeKKEf∂∞λ	-l⊗jλ¬↔j⊃λλT⊃J7+[5#"KK∂(_m⎇Xx=8.x{mlx=⊗h'x{{L<=⊗pg5⊃λ⊃$λJ77+Q"W↔πT_{{L<=⊗p'<{{Xl≡⊗pNeλh⊃λλT⊃J7+Q"W↔πT_{{L<=⊗p'5⊂H⊂dλλ⊃(λe7#"KK∂(
λ∀⊂H⊂dλλ⊃(λe!"KH)v⊂C!%P4⊂**β"KHYQβ"Ehβ(εE∃p¬ are as@MkeKHα↓β >dλλm⎇\⎇≤N\⎇~;L@P0P ,ist @!KeJA	KGCkβ≠∃↓∃≤π∩*R
_d(≠⊂∀\zεE0[2⊂;rH0y2P	Yqw`.cat%*-i`≥Nαβ?;SzβS#∃∧∧g-{]⊂≠pε i@PXA2M~Aβ≠,s∂S'}sL4.⎇εN≡∧↔⊗*∞Mrε≡⎇hnN]8p~λ64yjλ5zz8≥z⊂1<H∩Yq`/ncad∀T[S]≤@Bm[UghJT@JgGα{;∂π ∧RRε⎇nF`4λβ"NM→(⊂∪≤αont↓←@→β∞qβ↔cO≠S'lpλ∧VXε4i]∩U↔ That↓YSghαβ7πeε∪∃β↔LεFF/!Q&v}e\VoπO∀ε␈∩∞Mε*ε]↑π'J
H
.>	λ	&5λj)%%Hβ"JM~<h
≡h≥z∂∀≥~→$∞α2y6Zu0z4[w⊂1`/ndition on a lIst-cOnstructing function,
su@
PACf↓iQJAα3?33|εvNvtg.v>M⊗}rD∧S≡&}LVj*%APW⊗↑NW⊗w4∧S~B5∀RRpQ!PU&Tε∂⊗}]V.wN4π&z∧V6&␈L]R*R≡&*ε-zFBεM≡7'~≡7∨.\\Bπ&t6}wL≥⊗rπMRπ≡≥\PhVn]V⊗/$
v2ε]LVn.nN2r¬MRπ6≥NV*π,↑G/⊗l\BεO4∞Fzε,Tε
εM≡7"ε|dε&␈NLV"π≥↔↔≠4∞FF*↓Q&.f]\Vw'4
v2πMRπε≥≡'~ε≡,Rπ&Tε≡␈.,W∨ε⎇lFNvtVf.\]g'~
|bπ&TεNw∞↑Bεf≡>G~r
Mπ/≠!Q hRh(T<Ld
4,dX:Bβ≠8¬⊂()5*ε↔
.c!%PSvλ⊃"Y≠nL;6}π?7(∂πT⊗w≠N]≠⊗}Tε(
∧¬.c"KD9=	%$ε(_m⎇Xx=<{{\k<Z<\nK}↔.lm<\p~⊗|nn]Y7z2vVy2yz⊗|.]y→yz-|WnnnFB↔!'l⊂εE↔"S"εE↔⊃(εE*~2P34\9z⊂:~4w3P≥7P77]2P4yH:42P≥yrP7Y⊂17z~⊂∩Yq[w1pz	U⊂0w→⊂∩Yq[w9RU∞⊂∩Yq[w1pz	UεE4\P:yrY⊂:7P_:tv2λ:42P→4w0vλ64yzλ7zz8≥z≥P∩Lqww9IU⊂4yH:yrrλ:7P1≥tv2⊂≥42FE→7z:2Y⊂80t\9W⊂'≠{P4sλ;rP⊂~0r⊂;\4z:2[⊂∩Yr≠z2vRJ⊂9zqZ⊂:40]⊂4z⊂~w2{FB0q7z]⊂7zyλ92x9→yrw:_z4wwλ7s⊂6~yz9Vλ:42wλ∩[17]4∩U⊂→:w1z~ww9P≥wzv2λ40{2H12rwβE∩Yq[w9RU⊂*42H22s4[4z4w[⊂;wz[2⊂77]⊂40{→P12r[⊂⊂0yH1v2p\↔εEεBεE↔!⊃cdg⊂⊂bg*"T$j≥iQf"ajλ_]FE#i'jT≥FE&≠wuP0]⊂0P1[vx:z_z4wwλ0yP9Zvx62H0yP∩Lr7z2[mT TNT!∀nIU↔⊂*~4yP;Zv6⊂4[;7v;→FE↔!∪l FE↔RYqw[1pz-Xww9mP]a.MY7z2vVT⊂∀MJ⊂∀nnKεE↔!∪l!εE h i∃εE↔#T'jh≥CE↔#(βE∩Xg≠{P:4→P2{0[:pz4[w⊂7sλ∩Yr7]2vmTλ∀]T⊂
nRXP≤2z:i≠9P7z\⊂72rY2r⊂∩LT⊂∀RJ⊗⊂3t]4w3FB↔!'l⊂FE/RLqww1Xz-qw[9m`]P.]T⊂
nP≡@_ww1p]-T P⊂!∀]J⊂∀nP∂P∀∀ H↔⊂!∀JFE↔!∪l!εE"g"εB↔#(εB$s⊂:~2P:2\6tw0]4ww_ww24]4ww≠q⊂∩YY7z2vIU⊂92]8y72Y⊂0w<]44w3H7z42\⊂:40[εE∩YJ⊃TRUλ:42wλ:42P≠4yz⊗Xww9z≤:qz4[w⊂;w]v2⊂⊃→rz⊂7Y3⊂7wλ:42P≥y7w3H37wzλεE0w→⊂;wz[2⊂77]⊂3rw→y0z2H0P⊂6~yz↔εBεE yH897vZyrr⊂≠w⊂=|[w∀(_M∀␈⊗⊂~2y2P~yP0Pλ24y2Xz⊃⊂2→s4w4]4ww⊂≠s⊂∩Y\2{2y≤rRU↔βEεE↔⊂"cdgλ)bf"Ph∧ 3;TABIT1(18	;CROUP;
.BOXA
.P23:
revers@∃7q:@p{97]UYY7qt@2@PRv~∃p@KKh∀T@2A¬aaK]⊃3eKm∃`O⊗←∪↔OR\π¬mkαxsmlx=⊗lm<\p~⊗|.]Tλ∀n`≥] 
α.BOXB
.END
.FP
This revep¬gS]≤AMk]
iS←\↓SfA]=hACf↓KMMS
SK]h↓CfAi!JAae∃mS←kLA←MJ8~∃/SQQS\AQQJAG=]gieUGiS←8AWLAβ##∃β⊗+[↔K≤∧V"εM≡7"πMRα+<≡πε.lDRRεn]f∨&≥⎇`hV≡4ε≡∞MH	,D≤Y<\=→9
O+H⊗-}(≤z
};→⊂→{0v:Xz2P9[vrz4~w3P6~urP∩Ly2{"\9rmT⊂P!⊂!H"∀nBJεE:7H9rrP≥42P2~s34q]v:<WβE↔"g⊃εAεEβ$z⊂∩M4yRUλ87yyZq62P≥7P;y~z2P0H24y2Xz6<P≤2qzy≤t{2P≤2{2y≤tw3P→:w1z~wwεE≥tz4⊂≠7P0z↑4v4p\<P3:[1z4w[9V⊂7≠P3:w_z4ww≤P7z4→y⊂:4_w⊂:4→P894[tz4{→yV⊂0[2εE;Zz4⊂7≠z⊂6zXt⊂1v_y4z<K⊂+rP≤t0v6λ82y9Zyz⊂⊂_2qpz\rP4zλ4yP0H3wwrλ2|0v\62P7YεE⊂2~yqw{→y4w3H:42P→rw2y_v⊂1p\rP7sλ:42P≤2qzy≤tww⊂_<P1p\2s:vβE1ww≤tr2y_z4wwλ7s⊂2↑0vx6→yW⊂&→z⊂:yH1pv6λ:42P→:w1z~ww⊂∩Ly2{∩J↔εEεB+rP1[w9tr→y⊂:4→P3rw→y0v⊂_pyrP→4y9z⊂0w2βE87y]87w2H:42P≥2y6t[0z4w[⊂1ww→4z4w[9P⊂:[:4v⊂≠0z2y⊂!ww≤tr2y⊂37yλ2|0v\62VεB∩Yy2]-T QP⊃aQb
nRU↔λ*44yH9t7z[2⊂2{_v:pz→P:7P	YT"⊃PQa⊃`JRU↔⊂∩7{P1Xw⊂;rCE1ww≤z9:q]⊂:44\P64y]⊂1<P≤2qzy≤t{2P_pv69H7s⊂∩Ly2{∩J∨PεE⊂yyzvYP∩Yl	U⊂40\P;0v≥pP∩YJ Qa⊃PQb∀RJ↔εE'≠{P77]2P:4_z⊂∩YJ"⊃aQP⊃`TRJ⊂4yP≥42FE≥0v:rH7s⊂∩Lqww1Xz-b≥J!Qa⊃PTnRU⊂*42[⊂∩Yb	U⊂4yH∩Ys4\9z-y→{-y2\z-|.WnRU⊂
4z⊂4\P0v9[FE∩YY4y9z⊗y2{-↑.nRUλ1:z⊂≥40z would not help us sInce the recurs@%←\A[UghAe∃IkGJ4∃iQJ↓G←[a1KqSidAWL@↓iQJA¬eOk[∃]hR\4∀~∀]≥%∨+ l~∃⊃←\AGC\↓oJAO∃h@Jf!εG∧G∧RJT}FA/K1Xt~∀9¬∂∪8A)β¬%(dPdDXf`Rm∂%∨+@w'→∃π(@fl~∀]¬=1α~∃pQεA∧↓αS8z↓eKm6!αA∧AS:
∃q8zAe∃m7G←9GCi7∧vQ∧AS;:@4∃98@@@Jb!oJACIJAO←%]NAC→iKd@∀geKgQ7q:J(ACOC%\X~∃q8@@@@@@A	khAM%egh@↓oJAG¬\AOKP@Jgα∀bAMe=Z@Jg`\~∃9pzAeKY7G←]
Ci7M%egi7a:vQ∧↓εS;:4∃98z↓eKm7
←]GCQ7MSeMi7q:meKm6!εA∧Su;:
∃q8zAe∃m7G←9GCi7→Segimq:we∃m7eKMi6Qλ↓εA∧Su;;:~)98zAIKm7G=]GCimMSegQ7q:wIKm7e∃gi7e∃m7eKMi7q;u;;;:4∀]¬∨a∧~∀]∃≥λ~∀9β!β%Pv~∀~(]¬∂%≤A'1π(@st[rev[rest[x]]];
\\rev[concat[first[x];rev[rest[rev[rest[x]]]]]]]
.BOXB
.END

%1
.FP
Now, the termination conditions are simple. First %3rev[(#)]%* gives %3(#)%*.
But notice that the general case which we just constructed has %6two%*
%3concat%*s.  That means the shortest list which it can make is of length two.
So lists of length one are also handled separately: the reverse of such a list
is itself.
Thus the complete definition should be:

.BEGIN SELECT 3;GROUP;TABIT2(13,25);
.BOXA
rev[x] <= [\null[x] → ( );
\null[rest[x]] → x;
\%et%* → concat[\first[rev[rest[x]]];
\\rev[concat[first[x];rev[rest[rev[rest[x]]]]]]] ]
.BOXB
.END

We have only hinted at the issue of efficiency in computation. The question of
efficiency involves deeper questions of the evaluation mechanisms. We will
retu@I\Ai↑↓iQKg∀ASggUKfAC→iKdA]JAQCYJAISMGkgg∃HAiQ∀A→∪'@AKmC1kCiS=\~∃g
QK@7*β7?K*β∂?7εc↔S↔gI84)u∩⊗FVM∩∃↓
¬∩>	UuαV		¬~>VJ≤(b~&d)l4(hP1:N,→"πC∧¬FN≡≡M⊗}w4	v2∧β∩4j¬⊂<≤
M8x=
≥{\j!QKPQ(y3H⊃*πc"HEeKP;
D≥~→$∞~;9$	(→→.=9{@∞∞[y|L≥<h⊃M}H≠[ml>~<nM;Y`
\8z~-l<h_-lλ_9GA"P⊂~pε we ngwhad a machine comprisingthe primi@QSmKf↓QKeJ↓Cggk5KHXAQQK\AQQJAU=DASF4∃I←]∀\N~∀9 ~∀\\\A%\ACGQkCXAAaCGi%GJXA=LAG←β+KO∃bβS#'~β'β↔∞aβ7π≡C';∃∧εvNfD∞G/⊗d	w/"
mw"πMtε/F≡>Bbπ=qPV␈↑ λ
l>≥λ∞L<z`⊂T¬structurally simiLar to the original One-- is to program the
Simul@¬iS←\↓←DAi!J@EkAaKdDαβ7π∂FK;∃9rq9α/!βS#O→βWv≠!β?2βCK??∪π7MεKEβ←⊗KSC↔ph+≠?∩β¬β7∞≠#'≠*βS#π ∧εNr≥Fbπ∞-v⊗∞-→FO'∀λ
m≥≠λ≠M}λ→>
≡⎇λ∞=h≠⎇.$≠Y>∞D~[xD∞z;≠∧Y#"NMh≤z-↑;_=T~=λ
≥H≥→.-αyP7Y⊂897Yy0vyH37y_P72|≥⊂67{Yy⊂62]2v⊂6Xqt4w→V⊂2z_W⊗εE≥w:4vλ34w0[68P+YP40{→P0P8≤7sy0[P:40]⊂1pwλ12P2↑2qzz→r⊂1<H7zy⊂~0y2;Xy2W↔↔⊃εE"g"εB↔(*→
≥FE↔⊂"cdgλ**i'λ'g⊂⊃εQ→FEβEbWλ+W⊂"~u5yz≤0V⊂↔-b4uλ[Y.oλβ######
.EJD
.PT2∀9PT249PT2l~∀
∀9'&Q∪9ie←IUGiS←8XY dβAP≠R⊃Q"tTβ"JM→<Y$<Y(∞<α{2`2al ways oF interpre@QS]NAQQSfAβ∪↔7π⊗Yβ >dλFNV>>G,+C"H≥↑;{LT≥z≠d
_<h∞∞[y|L≥990∩λ0z⊂0H4∧evEl
∃Q%OQKd↓iQC\↓[CGQ%]JAYα;∨W∞;∃β#∂→β↔c∧+@⊗N]l6."∞Mε*π
Vv}\]f}rd
FF*≤7"ε|aPWπ-|wε∞β;:-lh~;D(~~,]	;⊂∩]2v⊂ ,anguage is that kf wp¬SiS9NACY≥←eSi![fAM=d~∃B↓]←]KaSgiK9hAQS≥P[YKYKXA[¬GQS]∀\A)sASGCY1r@AQ=oKmKHXAiQ∀AGQC9OKfA=H@~∃IKaeKMK]iCQS←\A→e←ZA5CGQS9JAi↑↓[CGQ%]JACIJACY0AI←]∀ACki=[CiS
CYYrhAMe←4~∃QS≥P[YKYKXXAQ↑ACgMK[EYdAQC]≥kCOJ0AC]H↓MS]C1YrAi<AQCe⊃oCeJ↓S]giIkGiS=]f\~(~∃αAIKYCi∃HAmS∃nA←L↓	SUWMieBOLAeK[¬eVAS9m←Ym∃fA←kH~∃ISMGkgg%←]fA=LACEMieCGPAICi∧AgieUGike∃fAC]⊂ACYO=eSiQ5f\~∃]JAKqAeKgf↓←kdA¬YO←e%iQ[f↓C]HA⊃CiBAMiekGQkeKf↓S\Ai∃eP↔Mε{→βπ↔≠SKπ≥#'?;_h+';&+C↔≠&+;Qβ}1β#?:βS#↔Jβ7πeε∪∃βK/βK↔O.sS↔⊃εK9β¬εkπ∂#Ns∃mβNs∪↔↔"β←∃β≡84+/≠∃βSF)β'∪.Eβ?2βπO'∪π∂SL{9↓∃7∪↔∨π⊗#3↔O~))β?2β←#↔&C↔Iβ&C∃β≠␈∪7π3O≠44+>K31β6K;⊃β
βK↔C⊗+O↔;&S'?rβ?9βλβ7π∂FK;∃9¬##'Mπ+O∃β}1βπ≥#Kπ∂&K?9βO→βS#(h+SK.)βO↔w≠∃β?2βS#∃πβK?∨⊗77'v9βOSNc∃β∂∞c3↔⊃α∪OSK.≠SWK.!βCK};Kπ7nK;≥	ph*←∃π;'31π≠↔∃βNqβS#O→β∂#∂βS↔IεC?]β&C'Mβπ∪?∨K∞k7';:βOSgf)β'Mε	β;π'+Kπ1h+K↔∨+3Qβ}1β←KO#';≥π∪↔CK/≠↔;S∂#'?9nK;∪↔ε+;∪↔w!α2&≥↓βCK};Kπ7~p4(∀TMβ←*β#π[*βCK↔6K?WOgIβK↔nK/↔"aβ←∃π;'31π≠↔∃β
β∂3?≡)βK↔fS'?w≠#'@hS↔S>+↔9β&C∃βO'∪W∂S/∪∃β?2βπ9β∞c∨?KO##5β∞s⊃βSF)βOS↔+∂SW⊗)β?→¬##∃β&S¬8hR←¬βF[∃β≡+↔9β&C'Mβ∞cK↔π'Iβ?9ε	βO7∞c1βO≡3∃i∧¬FO∨E\⊗f>}-↔&F↑4hWL]f"πMtπ⊗.>XD∧[~;L\<[≡$! [{D∧,|Y.>	*H∞MβP∩YJ⊃P	%*; S-expr algorithms tefd↓i↑Ae∃Gkd@	YKMh5C]H[ISOQhλA←\~(JgGCHJTAC9H@Jg
IdJT↓iVAC8ACi←4\~¬∪9IKKH0AiQJ↓S]gi¬]GKf↓←@→β≤¬vw'-x∧∞⎇≤],>≥<Y.∀_<∀\<Z;L@P4w⊂_w⊂0v→wy4j~6PεE≥<x4aXv6<P≤0y0v≠2vεE≥42P9]<r2P≠q⊂4w→:qz4]2P22Y4w4`4iof od∧AiQ∀AICi∧AgieUGike∀AoQS
PAiQ∀~∃CY≥←eSi!ZASf↓KqC[%]S]N8@~∀]≥%∨+ l~∃∪L↓BAgiIkGikIJASf↓IKMS9KHACLt~∀~(]¬∂%≤Aπ9)%∪Pv~∀]	∨1α~)>KKλ∀b@ttt@KKλ∀hbJb↓x@KK⊂JhdJDAx@K∃λJhf∀b@@~)J]N]|@ygKDAKYK4|@ttt@yS]⊃Sl|Ap@ygKD|~∀]	_∞bλhQ:⊗: h):~h+S#.qβO∃ε≠π9β-CC↔∂ βS=β6K;⊃β
β∂?;&KS'?v1β↔GβK↔O≤¬⊗}r∞⎇ε␈≡QQ'π⊗\M⊗≡∂LTπε␈=~FN}n4ε∂⊗T	M≥≠→9∧↑(∃
(≤Y,=y{Z/,<\hmβy⊂*~2@
%eD%4i%1's. 
α.APART
.GROUP
If the structure is defined as:
.BEGIN CEH
)I∪(v~(]¬∨1∧~∃.K∃λJb@htr@Kα*⊃∃Q
)E↓9rq↓↓↔,!∃QE+	↓4V);≥:z↓↓sO/	y↓iSi↓∃IB))sO/	β↔3.iy∃Ib))↓9rq1↓s≡+Eβ↔f+5y∃⊂I∃(∀Rr
>b⊂h):⊗t 4):54+SFQβ'~aβ¬βF{7?∨.s↔?W~βO/≡\Vv≡T
v2ε]LVn.nN2bπMVrπ|Tπ>NMDεF∂lTε
Q$&fNl\↔∩∩∞,V∨/.8
-⎇H≠∩-<(≥~≡λ→>∞<Z9-ly9λ
≥H≠∩.>8;⎇|Z=

<e@$	;Y→,\β"]
<Y(≡Y(≠nM→<@m|[<d
yH⊂m⎇]≤[mD≠~:lT~=→.,=~;md≠|H↓QI,s
≡	*H¬∂};{E
,le∨J#"N⎇~8z∧<Y(∞,;_=\λ≥≠d∞⎇8z∧_=_$∞⎇≤],>≥<Y.5WkC!%P4⊂**β"KHzSu4π1"QZ-l;≠≡$
9H≥
(≤⎇∞.8⎇≥.,(~<d→9R-l9λ≥m≡~λ_$Z>→,D≠];,,<H≠ld_{{.
{Y;NNh_<g!"KPHXp3Hλ83U⊃*)5∞c!%PSvλ⊃"Wi,X	,(π'O(	,X	-$V(	9(D-I&∀	91∧Vi,%eKH	,X	-≠DV#"Y%lkH↔d∧λ∂≤l←≤≤@∨λ≥≥≡P	YT∩U∂9r|8≤∨⊂↔⊂∂9r|8≤∨∩YTIUεE↔⊂'l!εB↔"g"βE↔#(βE:42[⊂;rP_pw⊂2↑82qjλ⊂7qq]y92w_ryP7Y⊂9rv→qz7iλ3:w1]4ww9H:7FE→|:90Xz⊂:4→P1wv\7w2w≥9P39≠vP:4→P9z9≥qz:i→Klw]P6p|H40{ %
noTiced thatwe are therefore dealing with essentially "context-free" abstract
data structures; i.e., those generated by context-free grammars. See#⊗↑[Hop#69]↑.←.
.APART;

Thus a data-structure algorithm tends to "pass off" its
work to subfunctions which will operate on the components of the data
structure. Thus if a structure of type %eD%1 is made up of components 
oF types 
%eD%41%1,
%`λJPdJbX4∀KKλ∀hfJbαaβπ; 4)↔,!∃QQ+	1βSF+9βSF)βOS↔+∂SW⊗)β/→ε9βπf;?K'&C5↓∃≤1∃)β|εε/⊗≡M⊗v:
⎇bα.X@RPh.O↔εN<≥FgJ
→g6}NlW
ε<≥Fg~
⎇bπ∨\,g.v>M⊗}w4∧S≡2VB∩+
∞Mπ⊗␈\⎇αα+<dS#"V∀π&xQ-ε∞vMH	$∞~→(∞>8Xp↔[x:z0]4ww9K⊂"pqZ⊂∩Ys	Z4RXH;tv&λ4w⊂:≥y7⊂1≤2puP≥x⊂4z≤P∩rb	Z4RXKεE*4≥yP⊂:~2P:<\2Vyz≤:qz:\2P7sλ:42P_pv6⊂≠w⊂∩YY∩U⊂;[zv2⊂_2]⊂εBεE↔!⊃cdg⊂⊂bg*"T$j≥FB↔!'l⊂FE/RLs-RrQ∩YnP∂P3mBLs∩Z_IYmRrQ∩Z_RLn]RYY∩Z→∩LmRrb	Z→∩YW]RYs	Z→RYVRrb∩M→RYnNRYs∩M~∩YmIrb∩Z
∩YnnCE↔!'V!εE↔⊃g"εE#(εE∃44yP~yP:4→P2yyYw1rP≠s⊂62]2v⊗{ZyrP8≤7sy0[vtw3N⊂;rP≥y4z2H∩Ys⊗λ3∩Z_IU⊗⊃W↔⊃V⊃Y∩Z~∩LFE4w→2x2w→2w:6≡P7s⊂≥42P9→x92yYw:0z~ww⊂7Y⊂:42Zy⊂20]0P9z≤:qz:\2yWεB∩Ys∩J⊂;tv≠⊂9:wλ897{~r2r⊂≥40z≥42P∩Ls∩Z4IXSyP_y2P0]0tv0X42W⊂βE yP≥pP;y~z2P:~2P∩YY∩Z4RLSyP;YP;tv≠⊂897X0q6<H4w;7ZrP1w[x:z0]4ww9H7wεE_wvx7[2w:9H7s⊂:~2P1w\92yx≠w24w→P∩rb	Z4RXK⊂*47\rP1w[x:z0]4ww9H0y2P~w⊂::\7εE2↑2qzz→r⊂1<H9zq3≥w1z4[w9P;Z4qt⊂≥rP40]2P:7H;y4z→W⊂*4~yP89≠qryyH7sεE→v0q7\0z4w[⊂:2y≠tw0z→yP;t→w⊂0v≠⊂9zq→:w1z~ww9P_y2P;\4z:2[⊂0w2λ0v6εB20z0H9z9:Xz:y2\P40{→P92qYt{2rλ1ww1\2z2P≤2x92\rw:0]4ww9K⊂$w⊂∪$ih⊂≥44yP≠rpw9CE:42H67{r\z⊂62]2v⊂3≥w1z4[w9P0\2P2|≤92yyYr⊂4wλ:2y6\P7s⊂∪$ih⊂≤94vt]4{2yCE0w2λ:42P→0z0P≤z9:q]:y2yH0y2P≤2x92\rw:2Y⊂4w⊂≥2y6yH7s⊂)Kr|89≤W⊂*4≥yP0zλ:42P~4st2\zεE6→{2v⊂≥rP:2[2⊂:7H:44w~P7s⊂_P20z_P9z9≥qz:y→P0yP_P1v0\yP7sλ12t0]4wy9NPεE;YP27w	z⊂1p\ehavior.
At the lowest
level, machine-language routines  simulate %6one%* of many possible representations.

This process of elaboration of abstract algorithm and abstract data structure
may modify the top-level definition of %3f%*. Implementation considerations
may effect some earlier decisions and require replanning of an earlier strategy.
At that time the complete plan should be re-examined; local  modifications may
hav@∀AOY←	CXAe∃aKeGUggS←9f\~∃∧Aae←≥eC[[%]NAgQsYJA%fA]←PAB~∃AC]CG∃BvASPASfA9↑Agk	giSiUiJAM=dAGY∃CdAi!S]WS9N\~∃%hA←]1rAQK1afAG=]ie←0AiQJ↓G←[a1KqSidA←LAQQJAaI←OeC5[S]N↓ae←G∃gf\~(_]'&!qC[AYKfA=LA→∪M AβaAYSGCQS←]f0Y djTtR~∀9¬∂∪8@E10H`DA)U%≤A∨8@E>Dl~∀]
@~∃)Q∀A]KqPAMKn↓gKGi%←]fA]SYXA∃qC[S9JAg←5JA]←8[ieSYSCXAAe←EY∃[f~∃%]m←YYS]N@↓G←[aUiCiS=]fA←8AICi∧AgieUGike∃fT@A]JAoS1XAIKMGeSE∀~∃iQ∀Aae←	YKZA%]ikSQSmKYdXAaS
VAC\↓S]Si%CXAe∃aeKg∃]iCi%←\AM=dAiQ∀~∃ae=EYKZ0AoeSQJAiQ∀A→∪'@ACYO=eSiQ4XAC]⊂AS\AM←[JA
CgKfEak]∀DAiQ∀~∃CY≥←eSi!ZAEr↓aSGW%]N@E5←eJA∃MMSG%K]hD↓ICiB↓eKae∃gC]i¬iS←]L\~∀~))QJA∃qC[a1KfAg!CeJA=iQKdαβ'7C|ε'&∞nDε≡F≡,⊗∨&↑-↔∨&≤>3RQ%e¬#&APRtiAPR+&∃b*R∧
v*ε←⊗nNlTπ&FT∞π⊗}-HVjεM⎇V∞Nd⊗v"≡G&.↑
Bπ&t∞&/π,↑6.wD	↔'~]F.n]nG
Q,↔~εL≡F
π>N'.∨NZ&/~aQ"ttAQ"+∪%dRRα
|Rπ⊗\mF.∨D
vrε}↑"αF≥nG.OM≡f*J≥F>␈-≡FFj≥f"πN/∩π&tWGπ,↑7~ε≡DhV≡4ε
∧I~5αnM≥6*εL≡F
o>N'.∨N↑&*ε\≥fOπ]L↔&Nltε7.l>FN}eaPRtiAPR+&5b*R∧
vFNLTπε/,mw⊗n≥lrα+&∀RRε≥lBα+&$RRb∞|Rεn≤⎇π"ε≡f*πMtεn}M≤gJπ=⎇V*ε|aPV␈↑$ε&.=≡6N}n5b¬≡⎇\W&F≥lrαε≡>7.n\Dπ&z,Rπ∨N.V∨'↑,Rεn≤⎇π"ε,↑G&/$&*π,↑π⊗/<]g&.AQ&∂~≥F>␈-≡FFjD
w∩π=⎇V*ε≥Lv␈⊗≡Mεjε]≤vG",Rε⊗↑NF/∩∞,Wε/<]g&.D↔~ε∀F∂&∀∞7'↔\>G/⊗UaPRtiAPR+&Eb*R∧
vF.d∞FF*∧F.≡≡=⊗}w4↔⊗*
\⊗&*D∞v*ε↑l⊗g.≡LRπ&T∧dM:∧ε7.l>FN}d
vrε∀↓PW⊗↑∞&/≡]nF∂&≥⎇bε}d∩ππ-|&f.UaPRtiAPR+&Ub*R∧
v*π,]⊗w&↑.π⊗/D∞FF*L↔&
↑>G↔.>NW⊗*
}W'π↑Dε∂~≥bε∞n>v/∩∞Mrε␈↑$ππ⊗|-F.jaQ"u¬F&@hRhjhU
≤7&␈-≤⊗fg∀
⊗rπL↑&o~
|b∧d~:βPh!Q"t∀Xy∀r∧z)u-β8¬⊂()5*ε6*.|∞,9X8lTλ≠-≥≠≤naQKT
εgC"KH)v⊂#!-;Y[n-8;λ∧π/H∪	~tλ→N]X⎇~-⎇W≠β!,9→{n-=~≠+Oβ"W∂D→=X-N8=~-⎇C"W∂G///'W//'D
;]→..≤Y=∧↓"W∨∧∧λλλ∧∧λλλ∧∧∀k9/∞≤H≠n↑≤≥=∧<h_-n⎇y<AQW≠β!,≠{8-≥Hλλ∧π/H∀e\>≤≤L↑|z;mnw∨β!%PSvλ!"KQ)hβ"C!*z→;L↑Y<H∞|(≥|M≡→(_m⎇<≥=↑H≤≤M||X;.5λλ≥m=→=L↑H≠_-l⎇89lT≥y(∞↑y+β!.y(_-Nx><d{h≥
∞[⎇9m∧_(≤m≥:;_.$≤Y<∞,<y;NL=~;md≤≤[l-→;+D↓"U~T≤≤[l<<|h
≡h≠;n,(_<∞<Y;ND~;H∀~~9m<K;↑Y;λ
L;Y⎇,≤y(≠
≥y(β!(StU
(3H≠n∧⊂3⊃iyλ_-lλ~<d
;|⎇∧
[⎇~,<88[T~;H∀≠_;L}89y$
~:y$	∩4t∧∞z~8m↓"\≤M≥8<Z-O(→→,≥≤h∃m≡~λ→≡_(≤nN]8u∞↑Y<kAQC"Um;H∃lT→→8-D≥z5
∧≠];,↑Z8x-D_;→m}Z=~
↑iλ∃
(≤Y.∞Y<p∩[80z4[w⊂8 2oblem
`as usuallq been settled in the tpansformation from Real-world qituation
to a numerical problem. One has to thini more explicitly about
representation when we deal with structures like arrays or matrices. 
We are encoding
our information in the array. But the preceding diagram occurs 
within the machine, even for strictly non-structqred
numerical calculation.

.BEGIN GROUP;TABIT1(25);preface 0 mills;
.BOXA
numerical => machine 
algorithm     instructions\|
\|  execution
\|========> interpret binary number as answer
\|
numbers => binary\|
            representation
.BOXB
.END
.FP
The encodings are done by the input routines. The result ob the execution is
presented to the external world by the output routines.

However, when  we come to data-structure computations,
the representation problem really
becomas apparent.  We have to think more about what 
we are doing since we lack certain preconcep@QS←]f↓←dAS9ikSi%←]fA¬E←kh4∃gkG AG←[AkiCi%←]f\↓≠←eJ↓S[a←IiC]i1rX@A]JACe∀Aies%]NAi<AeKaIKgK]P~∃CGQkCXAAe←EY∃[f@JYISeK
iYrJ(ACfA5CGQS9JAae=EQK[L\A/J↓I↑A]=hACiQK[ah↓i↑~∃→Segh↓C]CYeuJAi!KZAS9i↑AB↓G←[a1KpA[¬iQK[¬iSGC0AiQK=erXA	kh~∃QerAi<AKqaIKgfA=kdAS9ikSi%mJAi!K←er↓ISeK
iYrA¬f@~∃5C]SaUYCiS=]fA←_AICi∧[gieUGike∃f\~∃QQSfA%fABA⊃SMMKIK]hA-S]HA=LAiQ%]WS]≤XAIkα)β←#}c3eβ&yβS#*βπ∪[.sQβ?24+∂}kCWS/∪M9↓∧K;∪↔.!βS#*β≠'↔f!β/→ε≠?7C/#πS'}qβ#π~β↔cC∞s∪↔⊃π≠=β7.≠ 4+∂→βS=εkπ/∃¬##∃β&+K *∧∧&≡}↑∞W&/$$ε}↔=x↑→+H∧
⎇≤],>≥<Y$∞≤[xl↑|{|D$~<h
]|Y#!-;Y~,<=~=LT≠yH∞M→(≤∞-|→<D
→=Y-D_=⊂≥t4qtλ;rP9Z7zv2λ;4rkH⊃1wv\:z2y≤Q↔εEβE+rP~0{2P_v92pY<P9bYw⊂0@≤tvx6→P2|0[x62P≠q⊂:4→P92x≤2yrw≥0z4w[⊂⊂8)≠q62vCE4w⊂≥42P2~yqzy\tww⊂≠s⊂64\z⊗w7]0z4w[⊂12sZw74w→P4w⊂≡|ww9\T(_X∀␈↔εBεEεE!"cdS⊂#i'Uh≥b P$j_TZT]x≤2s0qYP_⊂6Zv69]CE↔!'V FE9Yxzrw_rn>εB⊂0v3[y4z4≠P≡←⊂∪$ih⊂→:w1z~ww.>βE.>⊂λ2{0v≥pz4w[εE.>∂↑↑↑↑O↑↑↑←λ4w:2\892zλεE.>λ⊂⊂⊂⊂λ⊂⊂⊂⊂λ⊂⊂⊂)Kr|89λ92yz[:⊂0yH0w9{Yy↔εE↔>εE9Yxzrw_rP.>βE⊂2|≤92yyZww⊂≡O⊂)Vr↑892y\tww.∨εEεE"g"εBεE*4→P37v≠7{tw→P9rq]4ww9H22pvλ;tz4λ92x9→yrw:_z4wwλ7s⊂1[vx62↑⊂20z_P9z9≥qz:y→P897X62vyCE4w⊂∪$ih↔λεEβ↔)iT⊃4s32\2w:4Xz4ww24s3→y2w:~pz4w[⊗(~_N∀FE↔⊃(εE*~4yP2↑0vx6→P;tv≠⊂22yXy4q2H0P9:Y4vrw≥0y<P→4s32\2w:4Xz4wwβE97z]4w2P→7y⊂8≠v<w7[tpv9H4w⊂9Y{2y0[⊂;0y~pq62\W⊂⊂εB+rP;Zv6⊂2→{2v7\⊂:44\P0v3[y4z4≠P:49≠zst⊂≤r{2y_v⊂9z_sryWλ+rP;Zv6⊂1→stwεB1<P2≠tw3P_P;2y≡P24y→qz⊗⊂_:z⊂9→x92yYw:0z~ww⊗r→x2w2→w:⊗⊂~vx62[rw:0]4ww↔βE+rP≥tv6⊂→w1wr→P87v≡w7vtXv9P0\P9x2Xtpv⊂∪$ih⊂≠4yz9H0w2⊂≥tv6⊂→|892\yP:4→PεE2~s32y→w:4p]4wwεB0v3w\4z46H0yP⊂_P&$iT⊂897Yy0vP≠x2y0]4w3P≠w⊂:4_z⊂92\92yb[:0z4[w↔εE∃t2w⊂≥44yP≤97sy_vP4yH1wvx≠2z2v≡P9x"Xts4rY⊂;rP≥tv6⊂≥42w⊂≤qy:z~w4⎇"H4z⊗εB0z:2[x:4w→P:7P≤rrP5≥yz⊂4≠{P6zXt⊂7sλ:42P≤97sy_vP0w→⊂20z_P9z9≥qz:i→FE4yH92x 2esentation and how much is essential to the 
algorithm.

You should recognize two facts abouerentiation algorithm for polynomials:
first, the algorithm operates on forms (or expressions) 
as arguments and returns forms
as values. 
Previously discussed algorithms have operated on simple values and produced
simple values. The differentiation algorithm takes expressions as arguments
and produces a new expression as value.
Second, you should realize thatthe  algorithm for differentiation is
recursive.  The question of differentiating a sum is reduced
to the ability to differentiate each summand.  Similar relationships 
hold for products, differences, and powers.
  There must be some termination
conditions.
Differentiation of a variable, say %3x%*, with respect to %3x%* is defined to be 1;
differentiating a constant, or a variable not equal to %3x%* with
respect to %3x%* gives a result of zero.  
This begins to sound like  the %2IND%*-definitions of sets
(in This case the set of polynomials) and the associated %2REC%*-definitions
of algorithms (in this casE differentiation of polynomials).
If this %6is%* the mold into which our current problem fits, then we must
give an inductive defini@QS←\A=H@A←UdAgKPAWLAA←Ys]=[SCYL\~∃)!←kOP↓a←Ys9←[SC1fAGC8AEJA¬aESiICeSYdAG←[AYKpX↓S]m←1mS]N↓iQJA=aKeCQS←]f↓←LAC⊃ISiS=\X~∃5kYiSAYSGCQS←\X↓]KOCQS←\X↓C]HA∃qa←]∃]iSCQS←\XAiQK%dAOK9KeCX↓M←e[¬hASf↓mKer↓gS[a1J~∃S_AiQKdACeJ↓IKgGISEKH↓S\A←UdA→∪M [YS-JA]←QCiS←8AoQKIJAiQ∀A←aKICiS←8@~∃aIKGKI∃fASiL~∃←a∃aCMIL\A/J↓Cggk5JAiQ¬hAES9CerAAYkfX↓iS[KLXAC]⊂AKqa=]K]i%CiS←8ACeJ~∃gs5E←YSiKHAEd@VX@(XAC]⊂A<vA]JAoS1X~∃oISiJ@∀fW7ple2JT↓S]gi∃CHA←_AiQJ↓kgkC0AS]MαKaβ;␈#πS'}q↓↓∃∨A-I∃Rp4*SF)β∨↔v+Kπ1¬#↔K5ε3?Iβ&C'MαdJNA7d¬⊗↑*
mw&∂M→vrε≡4α+⊃c≡π⊗.m∨αεv}L↔&N⎇buz*%aPPh)W⊗*≡&*π=⎇V*ε←⊗oεL↑2ε}d	⊗v6∨∧ε∞vD∞π⊗.m∨απ⊗↑
&/≡]nF∂&≥⎇g≠PQ%d∀,y→b¬$_)∃#∩ε6αc#U↔0hRhz$⎇-↓Q"t∀{λ⊂hUDV&Nvm∨¬gπ,XfO@Q$S_h!Q%gB/%3↔ME;2U←π?%kZ¬+3∪←≠[PhUO¬'JW+E%←C5+7K←+[PhRV⊃PRt){∧⊂h%h∃∧
*APRtYh@hPQ*v*α
mw:ε⎇≡f*ε≥dεNvN\7&OlTε&.m≥fO&≥⎇bε}d
FF*∞<W"ε|dπε}O≥f}n≤≥G_h.|Rπ>≡=απ&t6}w=≤F/∩d
FF*LV6Nm~FN}d∞vNfD
⊗w6⎇Nf*ε≥dεNvN\7&OlTε&.m≥fO&≥⎇`hV|dπ&/-↑2ph!Q"t∀Xy∀r∧z)u-β1Q"u¬F"@hRii@hRV"∩r*$44∞w∀∞F/⊗T
↔~ε∀∞ε}g≥mvnN≥E`hRii@hRV""r*$44N2∞∧S#
U$ε∞vD∞α+#$U"ε∂,Tπε}O≥f}n≤≥G~πMVrπMRα↔>]R⊂h-|bπαVF∩*R≥f"π∧VC∩*$
↔~ε∀∞ε}g≥mvnN≥E`hRhYd h!Q"t=)zUh%heh.⎇ε/⊗W!PRtiAPR+&∃b*R486}w>L⊗w'4⊗v"∞l↔⊗N≤-F/~≡&*πL↑&o~aQ"ttAQ"+∪%dRR~9≤bπ"VF∩*R≥f"πDVC∩*$↔⊗*∧∞F/⊗↑4π&F]dπ&FT∧'π⊗|NV∨"$↓PV}d∞B+#∀U"ε∞lDπ"+F$RRε≡4ε
πL↑&jpQ%dt`Q$S∪~dU"~≤≤dπ"+F⊂RRε≡4ε
πl≡&N∞-LRε∞lDπ"+F$RRε≡4ε
ε=⎇g∨&≥nBπ&]bh$.B+#∀U"π⊗≥≡6."∞Mrπ&Tπ"+F$RR+∞Mα+
∞	w>/$$εO~∀π&/-U`hRiiCXh$V#"rU$2≤Nd∞B+#∀U"εO4∩π&↑-Rπ&]bα⊗]≥g/~$∞B+#∀U"αε≡4ε
πL↑&jpQ%e¬#&APRt~λ∃∃ Q%d,tD∧%EC&∧ hRhz$⎇-π1PRtj↓PU>T∧εv␈tvO6T∩∧∀hdε&/<>&OπM→vrε|dπ&FT⊗⊗␈lTπ≡/D∞W≡Nltπ&FT∞7NwL∨αε}d∞π⊗.m∨αεv}L↔&N⎇g hPQ!PRt(XtLr
H∀∀MF∃β~↔8u∀⎇Zπ0hRjε∪#K!Q"t∀{λ⊂hSN
vgKkG#SjπJF/⊗WdπbβN
G/≠k7Gε}O↔c[g
⎇GKuQQ"u¬F!PSgL↑&kuG'#jβL=vw∨L≥g#r↓Q%cS'Tβg6≡-⊗∞⊗LWbh+G#SjπH

≥9<oK7≥→<MWNo≥↑[(∂.HεE.≥∞≡P≡ %xpt>[<variable>;<constant>]
\::= <minus><term>~∀9!(d~(yG←]MiC]hy8ttzy]k[∃eCX|@~∀]A(d~∀qaYkfy8ttzV@~∀9!(d~(yiS[∃f⎇8thz@T@4∀]!(H~∀yKaah⎇8htzA<4∀]!(H~∀y[%]cf⎇pttz@4~∀]!Pd~∀yYCeSC	YJ⎇8htz@y%IK]i%MSKdx~∀]¬=1α
∀9≥λ~(]β!βI(v~∀4∃∪hA%fAKCMrAi↑↓oeSi∀AeKGUegSm∀~∃CY≥←eSi![fAS8A→∪'@rAiQ∀A←]YdAae←	YKZA!KeJA%bAiQ¬hAiQ∀AI←[¬S\AC9H~∃e¬]OJA=LA→∪M AMk9GiS←9fASf↓&[KqAefXA9←hAi!JAa←1s]←[%CYf\4∃/JA9KKH@↓i↑Ae∃aeKg∃]hACIESie¬erAa=Ys]←5SCYf↓CfA&5KqaeL\~∃/∀AoSY0AI↑AQQJAe∃aeKg∃]iCi%←\~∃%\AYSMifAe¬iQKd↓iQC\A&[Kaaef\4∀]∂%=+ v~)→Kh@∃K$JT↓EJAB↓Mk]GQS←\A5CaaS9NAa←1s]←[¬YfAi<AiQK%dAeKAeKgK9iCiS=\Agk
P~∃i!Ch@~)BAmCISCEY∀ASfA5CaaK⊂Ai↑A%ifAkAaKeG¬gJAG=k]iKIaCeh↓S\Ai!J@~∃Y←GCEUYCer↓←LA→%' ACQ←[f\↓)Qkfh~∀]¬∃∂∪≤A
≥)Hv~∀]	∨1α~(KK$K_PJbyYCeSC	YJ|K_RJbFtFyYSQKeCX↓Ci←Zx@~∀]	∨1∧~(]≥λ4∃→Kh↓G←]gQC]ifQ]k[∃eCYf$XAEJ↓Ukgh↓iQJA1∪' A9k[Ke¬Yfv~)iQKg∀ACeJ↓CYg↑↓eKga∃GiCE1JA→∪M ACi=[f\@↓)Qkfh~∀]¬∃∂∪≤A
≥)Hv~∀]	∨1α~(KK$J(KLPJDy]k[∃eCX|∃LRJbzFy]U[KeC0|@~∀9¬∨1∧4∀]≥⊂~∀]βAβ%(~(]
 ~)/JAQ¬mJA]=nAga∃GSMS∃HABAIKaeKMK]iCQS←\A→←dAi!JAECMJAI←5CS]f↓←LAi!J~∃S9IkGi%mJAI∃MS]SQS←\A=LA←kHAa←Ye]←[S¬Yf\A%hASf↓iS[J↓i↑AI∃mKY←@AiQJ4∃iKe5S]Ci%←\AG¬gKfA→←dAi!JAeK
kegSYJAIK→S]Si%←\A←_AISM→KeK]QSCiS=\\~∀4∀]∂%=+ ~∃]JAW]=nAMe=ZAIS→MKeK9iSCX↓GCYGUYkfAQQCh~)SL@JMjJTA%fABA
←]gi¬]hA←HABAm¬eSCE1JAiQ∃\t~∀9¬∨1α4∀]¬≥∪≤A)¬¬∪(d b`Xd@Rv~∃qHJgj∀T←HJMpJT@u8bAS_@JgpzAj~)98Jb@A←iQ∃eoSg∀~∀]9λ~∀]	∨1∧~(]β!βI(~∀~(]∂%∨U ~∀]→ ~∃/∀~∃oS1XAeKAeKgK9hAiQ∀AH[←AKeCi=dACf↓BAES9Cer@↓→∪' ↓Mk]GQS←\A9C[KHJgIS→LJT\4∃)QJ↓CaaY%GCiS=\XAH∀gjJT=HJgp∀TAoS1XAEJ↓eKae∃gK]i∃HACfJgIS→M7jwa:JT\4∃'S]
JAG←9giC]QfAC]⊂AmCe%CEYKLACeJ↓E←iP↓eKae∃gK]i∃HACf↓Ci←[LX~∃o∀AGC\↓GQKG,AM←d↓E←iP↓←LAi!KgJA
CgKf↓ErAkMS]NAQQJAaIKISG¬iJ@JMSgS]⊃SlJT8~∃)QUfABAIKaeKMK]iCQS←\A=LAiQ∀AiKe5S]Ci%←\AG¬gKfA5SOQh↓EJt~(~∀]¬∃∂∪≤AQβ¬∪(HPb`XH`Rv~(] bpHt~∀]	∨1α~)8JgI%MM7jmq:@xtA7Sg%]ISmmk:@2↓7Kc7`wk:@d@bv@∃KhJT2@a:\\\AtJT~∀9¬∨1∧4∀]≥⊂~∀]βAβ%(~(]
 ~)≥←iS
JAoJ↓oeSi∀AiQJ↓CEEe∃mSCi%←\X@∀gSgS9ISlJ(AS]gQKCHA=L@Jg%gS]I%lJid∀b\~∃e←jAg!←kYH↓EJAB↓EShA]CerA=LA←kHAIKM%]SiS=\ACYIKCIrh@JgI%MM6blc:JT↓oSYX4∃KmC1kCiJAi↑@∀fbJT8~∀
∀4∃≥←n↓iQCh↓oJAQ¬mJAG=mKeK⊂AiQJ↓iKe[%]CiS=\AGCMJXAo!ChAG¬\AEJ↓I←]J↓M←dAQQJ~∃IKaeKMK]iCQS←\A=LAiQ∀AeK[¬S]S]≤AGYCMfA←L↓iKe[LAC]H↓a←Ys9←[SC1f}@~))QChαβ'M1εC?]β≡C?W3"β←∃β⊗+CK↔≡+;Qβ∨+7Mβ∞s⊃βC⊗{∪W∂'→|4(hR≠'K∨!1β←*β←'3bβK↔C⊗+O↔;"βS#∃ε{C↔K∂#'?;~↓)1↓Za↓51ε;⊃αrβπMβ∂#?7MPh(4)t∩⊗≡&rβSπO!E!M~In≡J⎇*Al4Rr
>bλh*q↔-⊃∃)↔2A∃E↓Z↓↔→%+	↓u↓+~B2V~)D4*b+⊗I∃R+→!∃
↓)↓↔2I∃E↓j↓∃NRLj⊗M∃λh*q↔-⊃∃)↔2A∃E↓j↓↔→%+	↓u↓+~6&:-→∃D4Ua↔⊗I*Q↔→!+	αy↓.1%∃Eβi↓∃N-BBQ∃λh):
⎇Bλ4)t*:⊂4Ph*←∃π;'31εs?]β/CS↔;"βS#∃εkπCCNs≥↓↔-⊃∃)β&yβ?∂∨+KK↔v≠↔Mβ}1β'vKeβ␈β↔Kπ&{KMβ↔Iβ7ππβ';≤hSS=β&CK↔∃n+3↔7.sQβ3O≠SMhhQ:
>Dλ4):∀*≡&9∧~⊗:R-∩&QlhR⎇↔⊗∩))↔→B)M↓∃H⊃∃Nm+H
∃Q
)Mm∃H→∃QI+~u↓↔2I∃E↓j↓∃M!.*I↔→B)d	↔2I∃M1α+⊗I↔2A∃d
+!E↔→J)E1↓.*I↔→B)d
∃#⊃↔→%+→%4Rr⊗:⊂hQ:
>D⊂4):∀*≡&9∧~⊗:R-∩&Qn=∩>V@hRW;π↔IβπCεc'∂π&K?;Mπ;'31π∪↔OWg!β'9π#←=7.c↔7↔w!β3'∨#Mh4Rr
>bλh*⎇↔-⊃∃)↔2A∃M↓+H	∃NZ)d
∃≥i↓↔→J)E↓uα)M!↔-⊃↔→!+H	↔→J)M1↓.*I↔→B)d
↔2I∃M%h):
⎇Bλ4)t*:⊂4Ph):
,:&9α≤*:R⊗∀JQmα=∩>VAXh(4)+
≠?Iε+cπ7εc∃j⎇.*I↔→B)M↓.←Am↓Jj↓↔→%+	↓u↓α)M"Be*Mαaβ⊃%∃)ph):≡∀zV@4T3?Iβ
β7?K*β∂?7εc'∂π&+⊃β↔F7C3*aβS#*βC?3Ns?7'∞a4)+_4):∀zb∧4U{a∃a∩))↓-β∪gi↓ZβT4)+λ4):∀zbλ4RrεBε∃ 4+←Nc1β*βSKπw≠3πS.!βS=π##∃β6{33?>K;≥βπ∪↔≠'Bβ;?S∂#'?9Ph):
⎇B∧4)+_4*⎇]Zzoa[∩um↓]Y*mIZRoeoUjumβ-ju↓↓α↓X¬+
S#'~β'Mβn+OO'/⊃βS#∞qβ'Qπ∪↔π3gIβ;↔.#MβSz4+*β↔∂∂+O∃β>)βπO∨+7∃β&CπQ↓Zβπ;⊃αQβπK*β';∂∪e9αN{UβOF{W3⊃ε3O=εs?S'≡(4+SFQβ?/⊃↓↔⊗∩))77∂βC';8β'Mβ∂βC3'≡3∃π#=β¬εcπK∨/⊃β∂3∂≠Mβ?2β↔cC⊗+OO'}sL4+&Cπ9βW+OQ↓gβ?3erqα3?}YβπQα)M#a~Y∂e%RCi
-≠⊃%:⎇α4):∀zbλ4Rr~&2`h)∃DhQ:
@hR≠K?jβS#'~β'Q∨~β↔πOJβS=β>+QβSF)β3'∨!β≠∨⊗ih4)tr>~&d`4)∃_h):
⎇B∧4*zBB2V~↓"⊗b¬!αa↓∩I↓↓"∧bVM↓E"&6⊗~↓I↓"$J6⊗M¬Iαi%JαU%$hQ:
>D⊂4)∃L
%1
.BEGIN TABIT3(10,28,39);CENTERIT;
.CROUP
∀]=]GJA→SYX~)≥WnA]JAGC8AG←[AYKiJ↓iQJA⊃SMMKIK]iS¬iS←\↓CYO←ISiQZ↓M←d@,AC]HT\@A]JAW]=nt~∀9¬∨1α4∃9I6α)O	↓Zβ≥∃*j{⊃∃O@))↓uε!∃O→z)+⊃∃∨A↓-↓*S⊃∃O:))?⊃+≠a8∀Rr
>b⊂h)∃DhQ:εB
∩P4(hQ:=)zUhαKQJ↓"Uy$∞{⎇;D≤y9'+i,⎇$π(	1*$9J	&4→H
dh	9E∀,(λπT	,j
	∃4k∧∧94I,e	,hd	9J$Vkλ	,ZI9J∧∧,yh∧\J),e∀,#"Ej∃C!%QPβ!.z→<LWWi,n<8{{LK⎇7(πT	94D\Jλ	&<H	9E∀,(hd4_;Y¬D	,hd4⎇~~.,⊗⎇7$π(	9*$9J	&4→h	,e), ∧∧λλλ∧∧λ¬@(≡h≥y$
;]~-\=→9∧8<[
≤<Kλ↓Q]y(
=Y(]]→<L\λ_;D∞;]z.<(_{n↑\y(
<Y+AQUy(
=Y(∞M99λ∞M→(_-L{|Z.M≠(→M}H≤}-\[{~,4→~9Ll<Y;NM8=~-⎇H≥≠d(≤|\z9Z,4β"\L↑≤Y<l]]_=
≥{H→M}H≤≠mO;[{-≤;≤kDλY;~,↑Z;Yd∞~_=∧
=8z∧x;H↓QXY(
L8<[L\λ→\M⎇(≤y,];Yh
]<⎇_-<<kλ∞|(≥z-Mλ≥<lT≥~_.Dλ≤Y.∞Y<y-n_=~-⎇Kλ_-lβ"[md≡};me∀
m¬∨H≥y$∞z;≠∧>_;-≥Y(≠n↑H→→,=<z;meWc"Eh4⊂4JA"C"AQKQtIz4∞c!%QR3	A"KQJ↓"U~T≤Y<n]≥λ≠ld→~9Ll<Y;NM8=~-lh	,nT*H~.4≥≠h,(_(
l=h≠
≡⎇λ≠ld≥~≤L\#"Y-L;9;NNnC"Ej∃M↓QKSS↓QI,L%d,(hjM→(≤o≥8[{∧∧,t∪
Zi*KAQKSS↓QI,LEd,(hjM→(→,lY8⎇∧
yH	&<~9YDUH≠|↑X=~-lh	9*$9Jλ∧VyH	,e),#!%SSβ!$,LkDV(hu
(→9Ll8⎇λ
|H	,lM9YI%$≠|→.,=~;Lt	94D\Jλ	&<h	9E∀,#"Eh4⊂4JA"KT
FMβ"AQKQtIz4β"EhTβ"JM≥<h≥[⎇~↑H≤_..λ≠yD∞~→(≥→{|M≡~≠.AQC"I&1"KSihq(⊂hYU⊃4AQKPSkλ#"Y.∀⊗yZ..⎇⊗⎇+Wt∪∃*;(ε(
M<⎇λ:∪∃4g4→~9Lk|y8m⎇Y⊗⎇+W}↔.lM9YVnM~<Y>7.}[(β"EhSv⊂AQI,+AQC"C!,⊗i,leYw)%%y	,o∧*H~.4→→9M≥Y9λ∞Mh_Y$∧,yJD∧,9	&<i*KlD,}λ¬4→h
DV9	*Lei,9∧U↑	,%a"KPI{⊂C"Eh4⊂4JA"C"AQKQtIz4β"EhTβ"J=h~→.,)|h≥[⎇~↑H≤_..λ≠yD∧,y~,lI*NAQI,c!%PQ1i→H∃⊂()5jε⊗m%Fn*.h83U⊃*)5∞c!%PSvλ⊃"W→.≠yZ<N>⊗⎇7':∩31*;(ε7
M<⎇⊗kJ∪∃4g4β"WK≠~<nKu∩3(Znh≤l\{{Y>7.y
≤YH⊗nM~<Y>7.}[.c"KK↔≠~.>⊗u∩)X4n⎇

<Y⊗n[.y~,lH⊗|l\{{Y>7.}[7#"EhSv⊂AQKQ3HA"KThY⊃0u∧ε#"KH~⊂4U↓QC"KHzSu4π1"KQJ↓"QZ-l;≠≡%D~→<LT|h_-d→>_-↑≠→+D
y(~mm⎇nC!%PSvλ⊃"Wy4,}
O∀
h≡T*Ky∧V}λ∂$∂(
hε∀*C"EhSv⊂AQKQ3HA KQj)u4β!%QTβ!*≤↑.AQI,c!%PQ1i→H∃⊂()5jε⊗-eFLJ.aQKPSkλ#"Y
≤YH⊗e
∪∃4d¬∃∩3(Zh⊗λ∃(⊗∀NP,.FB.≡v4\z⊂-h∪*i]P→4s3-J* fbTP,⊂,J]P,.NP24s→⊂-l≥V.nFE↔≡v4y]⊂-n(∪*i]PβE..6~yz⊂-W(&*iNPεE.↔.64y]⊂-j$Sbi]P⊗≥P24Y3⊂-lNl.n]CE...≠4yz⊂⊗j$fbT]P,]H24s3λ-l≥l↔nn]FB..24Y3⊂-l∞l.nFBεE.≡[4yz⊂⊗n(&*T]FE.↔64yzλ-n(&∃i]FE↔..64\z⊂-j∩fbi]H,⊂≥X↔]FE.↔.64y]⊂-j$Sbi]P⊗]XnnNFE..P.FE!'l!βE↔ h⊂i*εE↔≡T(&∃iP⊂∀∀&*iP
*$fbTP,⊂_
P∀*$SbiP,H_TTPTFE↔⊂'l!εB↔"g"βE∩XFB;t4qZ⊂1pwλ12P4[:2y8≤2z2rλ0y]εB↔!'l⊂FE∩YCE/|∃⊂∃P<J_P∃PP⊂εE	XFE↔⊂'l!εB↔#(εB'7{P~z⊂4yH1v2p\⊂:40]⊂;rP~0{2P≥42P9~st:⊂_w9{r\≥P4zλ4yP2\zpv6≡P1v2Xy⊂:4_zεE:~2P92\92yr[:0z4[w⊂62X{2yP≠zqt⊂≥7P12H22yt\2r↔⊂∃42y2H0y2P≠q;4w]yFE9Zvx64Y4qpz~ww9P≥t4qtλ;rP;[zv2⊂→|82q]⊂:7P~0{2P→7w2P_2s7y→P;rP≥wzv2βE1ww≤tr2yλ:44yH7zz8≥z⊂0qXrx:0X62W⊂∃44yP→|0vx≠2P4yH0FE8_y:4q]v0y6≡P9tv\62P1XyrP3≠y⊂0v→rq90ZqP9t[x64s~qpz4[w↔⊂+YP1pwλ2pyt[<FE;\4z2P_P&$iT⊂897Yy0vP≥7P82\37y6H9tvx≠4s4qXz4ww≤P64uYP:47\rP2|≤2qz2Y⊂42y→]εE6~urP9→x60qZw3P∩LX∃<∩LP1<P	YX∩U⊂0w2λ∩Y|∃RU⊂1≡P∩Y|	U↔⊂!≥z⊂:4→P3rw→y0vεB897q≠2vP7Y⊂;y4]4w3P≤tvx6~s4ry≤V⊂7yλ4w22Yr⊂7sλ92qwYw4⎇4[3PεE≥t0z⊂~yP0P≤tvx6~s4qp]4ww⊗λ4yP8]tz2P→4s34Xzv:↔βE P;Z7v2P_90w1Z⊂7s⊂_wvx:]2y⊂9Xtrw1YP40yH3y7{[⊂:x⊂_y7zw→⊂εE9↑vq7v~qP0w→⊂0v3Yq90tXP6pw~x:v0]4ww⊂≠s⊂2|≤92yyZww9Wλ'w2P≠s⊂:4→FE1y≥qtpvλ80y:≤P7s⊂≤zqt⊂_w⊂2w→2p{7\⊂4yP_P9wx~4yz4Xpz2rλ9tvx≠4s4r\↔εE#≠y⊂6w\2P22]0tv9H0w2⊂→|0vx≠2yP7Y⊂:42H87{r\⊂7s⊂≤zqt⊂≤|yz2[yP9bYFE/⊗d2pQM≤.o⊗λ/-fPaQ[Z↔o⊗⊂7\⊂/-SwyQ[M.o↔εBεE↔"S"εEβ↔≡≡0X9z90Xz4w3H397vH92x∨∂εE↔!Qg*∀(≠tw:9H:7P7≠z2TFBεE↔)Qf"ajλ_]FE#(εE∃44yP≤97q6→vP7sλ92x9→yrw:_z4wwλ4yP:≡x4qp[⊂7s⊂→0z0P≤z9:q]:y2FB0v3w\4z46\P92sXy262\yP7sλ;t0zλ60w3]psrP≡wzP:\rW⊂⊂∃40z⊂~yVεE≠w1rP≡wzP4_{2P2→qtr2Y⊂;t0]⊂:42H4w37\6pv⊂_v3wy~z46P~yV⊂8~quP0CE92x≤2yrw≥0z4w[⊂;t4Xt⊂6pZryP<[zy⊂0[3wy4]46yP_v2pw⊂"|0[tw2P≥42P$[:2y8≠0|P1→z;rr[εE:4→P0v3[y4z4≠P0w2λ:42P≤2x92\rw:0]4ww⊗λ0w2⊂_ww:4[:rP:≠P2|0[tw2P≡wzy⊂→2qtyZww9FB0yP<[zP92Y4w2P≡wzy⊂≠rz47Y↔εE$[⊂=|w[9yT(≠~∀␈λ;rP;Zv6⊂9YrP0FB⊂9ry~ryP7Y⊂92x≤2yrw≥0z4w[9V⊂2Xqt⊂1→qwvt[3P6w\2P0w→⊂6wy→P⊃2s→4qtr[:⊃εE_w2⊂2Xqt⊂9→xzty~w3P6[y2P⊃~w7{v→r3rQλ12tw→P1:t[:⊂4w≥7P:4→P0v3[y4z4≠WεEεB↔#i'UhεE$→y2SyH:42P	Yr4s→∩XP0[3wy4]46P3≠y⊂⊂∃H0w2⊂
↔εE∩LFE↔!⊃cdg⊂∃ a$jT_X⊗\V~→J]FE↔⊂'l FB24s3⊗z]|.H≡≡FE↔-tyt[24{-]nPP⊗rxP-↑≥znPεP_]P	rz∩UλP_.NFE.⊂→xP-s~y9z⊂⊗zn]P∀&*inHP64\z.-h∪*i]PβE..⊂→4s3⊂⊗yrqw[2⊂-zW]P<.NFE..λ24s3λ-z44\2⊂-zW]P<.W]FE.λ2xP-Y4y9z⊗zn]P∃$fbiWPP6~yz.-T&*i]HεE..λ64yz↔-j$fQi]PεB...⊂≤rqww→-zn]CE...λ24s3λ-z44\2⊂-zW]P<.W]FE.↔⊂64y].-j$Sbi]PβE...λ:44y→⊂-znNFE..↔⊂24s→⊂-yrXww2-]n]P<↔nn]FB.⊂∩r]∩U⊂H∩\a∩J.FE↔⊂'l!εB↔"g"βE↔ h⊂i*εE9rv2Xz⊂_]CE↔(≠M≥εE↔⊃(εE \P;rP≠rw:4[w2r⊂→py64Yy⊗⊂:~2P1z\92w:λ6pw4Y2yz0]4ww⊂≠s⊂∩YY4s3∩J⊂2w1[r2yP≥7wFE≠zqt⊂≠s⊂7z\⊂80y≥4qzv_y⊂92\92yr[:0z4[w⊂37\⊂87v≡w7vtXv9W⊂∃42P9Yx0y0]4wwεB7s⊂0[3wy4]46P3≤7vP9→x92yYw:0z~ww⊂4\P12w→s4qtXv⊂39≠vP0zλ62py]⊂:;wH9z0w→87tw≥9WεE⊃4y9z⊂1t0[3tw3H92x9→yrw:_z4wwλ9t7z[2⊂40]2P0P≠tw4vXv⊂2s→2qz⊂≠w⊂:4→P9z9≥qz:y→FE7sλ:42P_v3wy~z46Vλ1:z⊂	Yr4s→∩U⊂∩M5w7{\RU⊂:~0z⊂;_y4pq≠2yP0\2P92\92yr[:2r⊂_yP0z≠vyFE_w2⊂0H9zvP~yP92\92yr[:2r⊂_yP0P≠4yz⊂≥t7yrH∩Ys4\9z∩Ux0y:λ4yP∩Lh&*iIU↔εE∀rqww→⊗⊂92Xr0q4[4z<P≠s⊂:4→P0v3[y4z4≠P9zs→2y9P→y2pz≠<WεE∩7{P6]qt⊂7Y⊂∩Yr~s3∩Uλ92pv≠<P72Yr9P:≠P5w7]P0q7]z⊂:4→P92x≤2yrw≥0z4w[⊂0w2βE47{H1pw⊂≥rP4v\97{2H:42P≤2pr0X4v4z≡P7s⊂	Yr4s→∩U∨FBεE*4→P:yr\P7s⊂	Ys4y≤z∩U⊗λ∩YyrXww2∩J⊗⊂0w→⊂∩Yz~4y2∩J⊂0y2H77z⊂βE80y≥4qzv_y6<P≠w2vw[4qKR7{r{→y⊗⊂⊂≥42|P_y2FE≠wy2P≤2pr0X62P:~0w⊂∩Lqpy⊗Xr9∩Uqt0t[9W/Wλ+rP:\rrεE	Yyrq[w2∩Uλ:7P3Yz⊂:4→P34y≤z⊂0y→zvrw≥⊂:7P_P9zvH7y⊂8≤7r:q]⊂0w2λ:yrrλ∩Yz4~y2∩UβE:7P→rz⊂:~2P9rXww2↔βE+rP≥yrr⊂	Ys4y≤z∩U⊂≥7P2|≥90qzλ:42P≠x2y0]7y↔εBεE↔#T'jh≥CE&2z	yP22Y4w2P≥42P9Yv2qz≠y9]εBεE↔!⊃cdg⊂⊂bg*"T$j≥iQf"ajλ→]sy≠zx≥FB↔!'l⊂FE/w\-|.P∂≡P34\9z-|↔FE↔(∃→εE/Xy3RZRU-|↔P≡≡P≤rqww→-|.FB↔(*→βE/py→RZ→∩J-|.P∂≡P:4~y2-|↔FE↔!∪l!εE"g"εB↔ h T*εE↔⊃i'jhβE↔#(βE*42[⊂∩Yr~s3∩Uλ12qw[ry]εBεE↔!⊃cdg⊂∃ a$jT_ZV
→V~≠J]yrv→qz⊂→NFE↔#T'jhεB↔!'l⊂FE24Y3-z]↑.P≡≡W-tyt[24{-]nPP⊗pxP-↑≥znPεP_]@	rz∩UλP_.NFE.⊂→xP-w\-znMH(&*iWPP ,ist\[PLUS; 
\\ difF [arg%41%* [u]; x];
\\ diff [arg%42%* [u]; x]];
\ eq [op[u]; TIMES] → list\[PLUS; 
\\ list\[TIMES; 
\\\ arg%41∀TA7ktv~∃9q8AIS→LA7CINJhdα))αo-imβbmil4*eaβ3'∨"rnRLj⊗Mmh*rrbβπK≥+!I∃)¬[Vu@1Q%eeDFN6d6∂⊗tVC
*$7-k4∂¬mmt%* → %9B%*]
.BOXB
.APART
.END
.APART
.FP
Still, there is much of the representation present. Recognition of variables
and other terms can be abstracted. We need only
recognize when a term is a sum, a product, a variable or a constant.
  To test for the occurrence of a numeral we shall assume
a unary LISP predicate called %3numberp%* which returns %et%* just in the case
that its argument is a numeral.
Then,
in terms of the current  representation, we could define such recognizers and
predicates as:

.BEGIN "XX21" CENTERIT; SELECT 3;group;
.EQ
issum[x] <= eq[op[x];PLUS]
.EQ1(26);
\isprod[x] <= eq[op[x];TIMES]
\isconst[x] <= numberp[x]
\isvar[x] <= [isindiv[x] → not[isconst[x]]; %et%* → %ef%*]
\samevar[x;y] <= eq[x;y]
.PT18
.END
.END "XX21"
.GROUP;
.FP
Now we can rewrite %3diff%* as:

.BEGIN TABIT3(15,33,37);select 3;
.GROUP
.BOXA
diff[u;x] <= \[isvar[u] → [samevar[x;u] → 1; %et%* → 0];
\ isconst[u] → 0;
\ issum[u] → list\[PLUS; 
\\ diff [arg%41%*[u]; x];
\\ diff [arg%42%*[u]; x]];
\ isprod[u] → list\[PLUS; 
\\ list\[TIMES; 
\\\ arg%41%*[u];
\\\ diff [arg%42%*[u]; x]];
\\ list\[TIMES; 
\\\ arg%42%*[u];
\\\ diff [arg%41%*[u]; x]]];
\ %et%* → %9B%3]
.BOXB
.APART
.END
.APART;
.FP
Readability is certainly improving, but the representation is still
known to %3diff%*.
When we build the result of the sum or product of derivatives we use
knowledge of the representation.
It would be better to define:
.BEGIN "XX23" CENTERIT;SELECT 3;group;
.EQ
makesum[x;y] <= list[PLUS;x;y]
.EQ1(22);
\makeprod[x;y] <= list[TIMES;x;y]
.END
.END "XX23"
.PT18
.GROUP;
.FP
Then the new %3diff%* is:

.BEGIN TABIT3(15,39,51);select 3;
.GROUP
.p101:
.BOXA
diff[u;x] <=\[isvar[u] → [samevar[x;u] → 1; %et%* → 0];
\ isconst[u] → 0;
\ issum[u] → makesum[\diff[arg%41¬*[u]; x];
\\diff[arg%42%*[u]; x]];
\ isprod[u] → makesum[\makeprod[\arg%41%*[u];
\\\diff[arg%42%*[u]; x]];
\\makeprod[\arg%42%*[u];
\\\diff [arg%41%*[u]; x]]];
\ %et%* → %9B%3]
.BOXB
.APART
.END
.APART
.FP
In the process,
%3diff%* has become much more understandable and, more importantly, the details
of the representation have been relegated to subfunctions. Changing
representation simply requires supplying different subfunctions. No changes
need be made to %3diff%*. There has only been a slight decrease in efficiency.
The termination condition in the original %3diff%* is a bit more succinct,
but incorrect.
Looking back, first we abstracted the selectoR 
functiOns: those which sel@∃GiKH↓G←[a=]K]iLrA]KahAoJ↓CEgiICGiK⊂AiQJ↓eKG←≥]SuKIbt~∃QQJAaIKISG¬iKfA%]ISG¬iS]N↓oQSG AaKe4AoCf↓aeKg∃]hvA→S]CY1rAoJ↓[←IS→SKH~)iQJA
←]giIkGi←IbtAi!JAMk9GiS←9fAoQ%GPA[¬WJA]∃nAiKI[f\~))QKg∀AiQe∃JAG←5a←]K9ifA←_Aae←≥eC[[%]NtAMKYKGQ←efX↓eKG←≥]SuKIfXAC9HAG←9giek
i←ef0~∃oS1XACaAKCdA¬OCS\↓←\Awe←\Q \jS|A%\ABA⊃SgGkMgS←\↓←LA≠
πCei!rOfA¬Egie¬GhAge]iCp8~∀~∃QQJ@JMISML∀TACY≥←eSi!ZASf↓CEgiICGhA9←nXA%\AiQ∀AgK]MJAiQ¬hAiQ∀AeKaIKgK]QCiS←8~∃←L↓iQJA⊃←[CS8AC]H↓iQJAIKaeKMK]iCQS←\A=LAiQ∀AMk]
iS←]LAC]H↓aeKI%GCiKLAoQS
P~∃[¬]Sak1CiJAQQChA⊃←[CS8AQCm∀AEKK8AKqiICGiK⊂A←kh8A)QSLASfA=kd@JedJT[5CaaS9N~∃C≥CS\v↓oJA[¬aaKH↓iQJA⊃←[CS8A←L@qa←YrxOfAi<AYSgQfAC]⊂A[CaAKHAi!J~∃G=]gieUGi←eLXAgK1KGi←IfXAC9HAeK
←O]SiKefAQ↑AYSMh[KC9SakY¬iS]N↓Mk]GQS←]f8~∃)QUfAiQ∀AICi∧Aisa∃fA←L↓iQJA¬eOk[∃]if@∀gjJT↓C]H@∀gpJT↓CeJ@qa←YrxAC]HymCdx~∃eKMaKGi%mKYr0@Jm]=hJTA1SghA¬]HACQ←Z\AQ↑@AgQeKgf↓iQSf↓a←S]PAoJAMQ←kY⊂A[CW∀A←]J↓[←eJ4∃ieC9gM←e5CiS←8A←\@JgIS→LJT\↓/JAQ¬mJAMIKckK9iYrAMCSHAQQChAQQKeJ4∃SfA∧AgkEMiC]i%CXAa¬eCYY∃XAEKQoKK\↓BAICQBAgiIkGikIJAC]⊂AiQJ↓CYO←ISiQ[LAoQS
P~∃[¬]Sak1CiJA%h\A!¬eCYY∃YS]N↓iQJA	≥AI∃MS]SQS←\A=L@ya=Yr|A=\Aws=\Q bPrS|X↓oJ@~)oeSi∀t~∀~(]¬∂%≤A)β	∪(dPDjXfr$wgKY∃Gh@fl~∀]∂I∨+ ~(]¬∨1∧~∃IS→M7jwa:@x{q7Sgi∃e[7kt@2AI%MMiKI[7jwa:v~∃pASggU[7k:2A[C-Kgk[m9ISM→7CeN∀hbJUmk:vAa:v~∃q9ISM→7CeN∀hdJUmk:vAa;:v~)8@KKPJT@2Js∧JM:~∀]¬!β%(4∀]¬∨a∧~∀]∃]H~∀9¬∂∪8A)β¬%(fPbdXhfXTjRwg∃YKGhfv~∀9∂%∨+@~∃IS→MiKe57jwqt@x{9mSgG←9gi7kt@2@`l~∃8A%gmCemk:@2↓7gC[∃mCe7`wk:@d@bv@∃KhJT2@a:l~∃8A%gae←⊃7k:@dA[CW∃gk[7q[CWKAe←I7qCeNJPbJU7U:v~∃q99IS→M7Ce≤JhdJ)7k:v↓q;:v4∃99[¬WKae=I79CINJhd∀U7k:l~∃99qISMMmCeNJPbJU7U:vAqu;:v~)8@KKPJT@2Js∧JM:~∀]	∨1∧~(]β!βI(~∀]∃≥λ~∀4∀]∂%=+ v~(]
 ~))↑Ag¬iSgMdA←kd↓G←[a1CS]h↓←LAwe←\Q DpdS|↓iQChJgIS→M6bvc:Jb↓OSmKLABAI∃MS]K⊂~∃eKMkYhX↓oJAg!←kYH↓CYg↑↓CIHt4∀~∀]	∂∪≤↓)β¬∪PdPb`0ddRwM→πP@fw∂I∨+ v4∀]¬∨aα~∃9⊃SMLJdNJU7TvAq:xzA7%gmCemq:@2↓7Sga=Ys7kt@2AI%MM7jlAq;:l@KKh∀f@2@∀s∧Jgt~∀]¬=1∧~∀9≥λ~(]β!βI(~∀]→ ~∃
%]CYYdXA]←QSGJAQQChA=kdAC	gieC
iS←\↓ae←G∃gfAQ¬fA[CMWKHAQQJA←IIKd[⊃KaK]⊃K]GJ4∃←LA
←]ISQS←]C0AKqaIKggS=]f\A∃qCGi1rA←]∀A←LAQQJAe∃G←O]%uKef↓oSYX↓EJAg¬iSgM%KH~∃	rAiQ∀AM←e4@@JgTJT\~(~∀~∀4∀]π9(Q!e=EYK[LR~∀]A(dh~(]≥_~(b\FG∃qiK]⊂AiQJ↓mKeg%←\A←_@JgI%MLJT↓←LAs=kdAG!←SGJ↓i↑AQ¬]IYJ↓ISMM∃eK]i%CiS←8~∃←L↓a←oKIfAgk
PACf@Jg=mpv@gtJb\~(]≥_~(d\FG∃qiK]⊂@JgI%MLJT↓i↑AQ¬]IYJ↓k]Ced@A[S9kf\~(]≥_~(f\FG∃qiK]⊂@JgI%MLJb↓i↑AQ¬]IYJ↓ISMM∃eK]i%CiS←8A←LAQQJAiISO←]=[Kie%FAMk9GiS←9fX~∀∀ggS\∀bAC]⊂@JgG=fJbA¬]HAi!KSdA
←[a←MSiS←8AoSi Aa←Ye]←[S¬Yf\~)
←dA∃qC[a1JASh↓gQ←k1HAQC9IYJ@∀ggS\∀pdJg`FVGG=fQpJ`fJfF,FkpF4dRJb8~∀]≥0~∀h\G/eSQJAC\↓CYO←ISiQZ↓i↑AQ¬]IYJ↓S]iK≥eCiS=\A←L↓a←Ys9←[SC1f\~∀_]'&!	CiB↓¬CgKLXY dH`tR~(]
 ~)∨]JA=LAiQ∀A[←e∀AS]iISOkS9NACaAYSGCQS←]f↓←LA→%' ASLAS\AQQJACIKBA←_~∃ICQBAECMJA[C9COK[∃]h\@4∃∪\AQQSfAMKGiS=\AoJ↓S]ie=IkGJ↓iQJA%IKCf↓C]HAMkOOKMh~∃Q=nA→∪M AGC8AEJA¬aaYS∃HAi↑↓iQJAAe←EY∃[f\~(~∃αA⊃CiBA	CgJA%fABA
←YYK
iS←\↓←LA←	UKGiL~∃i←≥KiQKHAoSi ABAg∃hA←L↓Mk]GQS←]f↓i↑Aa=gJAcUKgiS=]fAC	←khAQQJ~∃=EUKGQfAS\↓iQJA	CgJX↓i↑Ag∃YKGh↓←EUK
ifAMI←ZAi!JAECMJXAC9HAi↑↓G←]gQekGh↓]Kn~)K]ie%KfAS8AiQJ↓ECgJ8@~∃aaeKgMKHAI%MMKe∃]iYr0ABAI¬iBAE¬gJASLAC\A¬Egie¬GhAI¬iBAgQekGiUeJ\~)/JA]∃KHAi<AY←G¬iJAS9M←e[¬iS←\↓S\Ai!JAECMJ\~∃]JAgQ=kYHA	JACE1JAi↑↓CgVAQQJAgegiKZ↓M←d@↓B@AgAKGSM%FA←E)KGhA=d~∃o∀AgQ←UYHAE∀ACEY∀Ai↑AACeiS¬YYrAMaKGS→rA←kHAeKcUKgh@ EMS]⊂ACYX4∃E←←-fACE=khA→%' DA=d@EM%]HAC1XAE←=WfAC	←khA1∪' AAkEYSMQKHA	KM←e∀@brnTDR\~)/JAg!←kYH↓EJAC	YJAi<@ACI⊂AK]iISKfA¬]HAI∃YKiJ↓K]ie%KfXA	khAo∀AoSY0Aa←gQa←]J4∃iQKMJAWS9IfA←_AeKcUKgif↓k]iS0@AYCQKd\~(~∃)Q∀AeKaIKgK]QCiS←9CXAI∃iCSYLA←LA=EUKGQfAoS1XAEJ↓gkaaIKggK⊂ACfAUgkCX0AC]H4∃oJA]SYXA
←]GK9ieCi∀A←\AQQJAC	gieC
hAae=aKei%Kf\~)∪\A←UdAMSIghAKaC[aY∀XAiQ∀A←EU∃GifA%\AiQ∀AICi∧AECg∀AoSY0AeKaIKgK]P~∃G←9giC]QftAC8A←EU∃GhAo%YXAQ¬mJAB↓]C[J↓C]HA∧AG←Y1KGiS=\A←L↓ae←a∃eiSKLAC]H4∃mCYUKf\@4∀~∀]≥%∨+ 4∀]¬≥∪≤A'∃→π(↓Dw≥∨→∪→_wA%
β
@`A5∪→→&m∂%∨+@v~∀]Q+%≤A=
@D∀DXDFλXD∧D0E>Dv4∀])+I≤A∨≤D≤DA→∨$@D∀Dv~∀9¬∨1α4∀]↔%,~∀~∀@@@@$ ε∧∧λ∧∧∧∞λ∧∧∧∧D~∀@@@@@@4Aae=`b@4↓mCXbh~∀∩λ∧∧∧∧λ∧ε∧∧λ∧∧⊂~        ~ prop2 ~ val2~
             # # #
	εαααααααβαααααλ
        ~ propn ~ valn~
       	%ααααααα∀ααααα$  		  
.BOXB
.END
.LE(6,An object representation)
.PT24
.APART
For example, a  data base dealing with business supplies
might have objects named boxes. Each box has properties like 
size and contents.

Not all objects need to have the same number of properties. For
example in a data base  whose objects are bibliographic references,
books need not have page references, whereas journal articles require them;
journal references don't include a publisher Whereas books do.
The programs which manipulate the data base must be structured to
take changeablility into account.

.GROUP;
Here are some examples: the first↓←]JA]CfAKaieCGQKHAMI←ZAi!JAgS⊃JA←L↓B~∃1∃e←pAACaKd↓E←pv↓iQJAMKG←]⊂A[SO!hAEJ↓BAeKAeKgK9iCiS=\A←L↓BAES	YS←OICaQSAK]iIr~∃M=dAiQ%fAE←=V\~∀9¬∂∪8A'→∃π ⊃β∪Z:>~Lb1nB∀*~ε∞*↓Aα6Lb2Mn=∩>VAXh):R-∩9α>41↓	∃∩a	
	b⊂		1∃y	l4RrRVJrα> 2∧!b∩∧iz"α∩T'0hRh)uDλQ!PRα∧∧αI  ⊂⊂   8⊂   ⊂⊂   ⊂⊂"⊃PRα∧∧ααα∧β"∧t→XRα↓$∧β#β'⊗#+B∧∧↓Ph!⊂`⊂⊂   ⊂⊂0  ⊂⊂   ⊂⊂   @h$∧ααα∧∧α↓R
9∃T(λεDπ,+f$≡λ&∀εC"A⊂@@@@ @@@` @@@@ @@@@ Bβ"D∧λλλ∧∧λεHλ9s∪tDβHλλ
y∩5⊃$∧λλεAQB!@@ @@@@ `@@@ @@@@ @@B↓QHλλ∧∧λλλβ$⊂33JDλεH∧ε,λ∀HX34h∧βC"H∧∧λλλ∧↓) @@ @@@B@@@@@ @@@@ @Iλ∧↓"(λ↓QKQ3HA KP*λ4Uβ!%PQ1i→H∀q)H0uλ'sSqI→∪∞t
(1P0hTλ∪)→∪∀nhzSu4π1"KU
ZSH∪hhHλI$%λHhED@HK∧+hNc!%U∃4Id∪sH∧!HH⊃IzHλI$'c"C!$λλλ∧↓$@@ @@@@ `@@@ @@@@ @@@@ @@@@ @D#!$λλλ∧∧λλεDλ55∩	zHεH∧∧λλ⊂)I⊃3K∧	Sr∪ED∀KHβ!"B!@ @@@@ @@`@ @@@@ @@@@ @@@@ @@@A↓"Hλ∧∧λλλ∧βH∃∩*I⊃(λβ$∃∩⊃$λ3P5	y6(∪hd∪∩4j∧εC"A⊂@@@@ @@@@0@@@@ @@@@ @@@@ @@@@ Bβ"D∧λλλ∧∧λεH
K4⊃(∧∧εHλ∧∧λλλ∧∧λ⊂Siyhλλ∧∧λλεAQB!@@ @@@@ @`@@ @@@@ @@@@ @@@@ @@B↓QHλλ∧∧λλλβ$∀∃0IDλλεD∧λλλ	XqtP*u2∩3	Dλλλ∧βC"B `@@@@ @@@` @@@@ @@@@ @@@@ @@@@!β"H∧∧λλλ∧∧εH⊃λ~⊃(λ∧βHλλ∧∧λλλε↔-mb$∧λλλ∧∧εC"D∧λλλ∧∧α) @ @@@@ E@@ @@@@ @@@@ @@@@ @@I∧∧α"(∧↓"KPI{⊂C"Eh3Qβ!(z=Y-d_(→≡_(_L≡y(≠ld≠xZL\⎇≤k∧∞y(≠L\9λ≥
t_Y(≤[→(∞Mh≠8-m<≥;≡→(≥
<y(
|ZY8nNh~;AQ[98-m;YyN]λ≥x/≡kH∃lT≥z;
D≠[⎇∧9→≤L↑|h≥
(≤≤M|[→;.4≠yHL<z9mm;Yc!-;\≥.D_;Y∧
⎇=≤∞↑λ_N↑λ≥z-Mλ_{mly<[D
⎇<\l]≥Y<d∞{{→-O(≥z.Mλ≥~T≤≤[l-→;<aQ[yH∞<;8;NM8|h
|H→_.L(_X.<(≤≤M≥:=~.l<nH

⎇h_l≥H≥y$∞<y(∞M→(~-l[|[,≡~;{D
;H≥
(β"L,<y/aQC"C!);H≤L↑=9<nM;Yh
≥Y[|M\=~;md→\[mT_(→≡_(_L≡y+λ∞|(≥≡.
8x;
O(λ≤n8z9O⊃"\_..λ≠yD∞~→(∞,<=9.>λ_;LD→>≤\⎇λ≥
(≤}.>→;(∞Mh_{m\(≥<∧∞z=~∧(≤y.D≠yH∞
||z,-;~=
≤<c"N⎇~8z∧Z=λ
}<H→↑x|Z.∞~;{Ed⊃[|D>_;.
→+λ∞M→(≤L↑=9<nGHλYM≥Yλ_-Mλ_[m⎇|c"L≤[⎇=∧	∩4t∧%λ≤|\z9Z,↑h≥~≡λ≥y$<Y(
≥]→<L↑⎇→9∧
{[≡$
;H_M⎇z|k∧
[⎇λ
≥H~[n↑[X;↓QX<]
≤{→<d
|H_m}<\q$
[⎇→.7h≥~T≥≠|
≤h~<d∞|→8m≤Z99∧∞≠h_LT∪∩4j¬λ_].Dβ"]
(≤}.>→;(
≡h→\L\(≥≠d∞y;⊃,>λ≥~T≠⎇~↑H_{m↑≠{Y-n≤nH∞M→(_.↑~≠|ED≥~→$∞~=≠Uβ"]
(≤≥,-~<z↑H_;LD≥~→$_=→$
yH≤∞\[~8l≡~;{Ed∃~→$
xZY,>≤h≥m
8zλ≡Y(≤n8z9M≤9β"L≡Y(_l≥≠→9∧∧,X{mn⎇_;NNi,+∧∞~→(∞]\|→,=9Z9,D_{{.
{Y;NNh_<LT	,]L≡Z88ML<i,%a"P(∞,<=9.>λ~<d(≤⎇∞.8⎇≥.,(λ_l≥≠→9∧(	,N=≥→.-I,(≥Yλ_m⎇\z<nNh≠yAQX;H
}Y→<L\λ_{mM→8⎇
≥{H≠ld_{{N>_;]∞4_;Y∧∞X<Z,≤[→<ea"U~T→;→-\;]≤d
;H≥
(→_.L(_X.<(_<LT_;≤mt≤_=∞L<[\g4→[|D∞~~<d>_;.
→+λ∞M→>#!,{{]≥;H≠mm≡(_m⎇\⎇_-n≤nh∞>8zλ={\⎇≥]λ≤≡≥→<Mnh_<LT_;≤mt_x;
L9λ≤L\{|Y∞5C"U
(≤≤M|y<|d
yH→
≡x{⎇L↑Z;Yd∞z→=
<H≠n$≠[⎇∧(≤Y,=|Yλ
≥H≥~T→_=∀_X<lQ"[8.Lz→<d∞~→(∞,<=9.>λ~<dx;≠\λ	,N=≥→.-H≠8.Lz~;Lt,+C!!"C"J|(→→.<|Z8LT_(≤m≥<≠→$∞_=≥↑[H≠,≡_z→.$≠X;,\λ	,m\=_z∧V+H∩.D→>≤\⎇≤c!.≥{h≡Y⎇;,]]≤kD
~→(m<\⎇∧<Y⎇-\;]λ
≡h_(={\⎇≥]λ≤≡≥→<Md_x;
L9λ	&>_=	&∃C"U
(≤y,={Yλ≡Y⎇;,]]λ∧Vy>≤∧V#"\L↑≤Y<l]]≤h∀≤Y<.\<⎇∞d
=λ≠,∨(_Y${{\nL;]∧
|H~.D≠8>${{]≥;H≥L≡Z88ML<kC!)9H~.D→≠y.4_{{NL:;H∞l<Z8,-→<k∧∞~→;D∧≥~→$∞_=≥↑[H≠,≡_z~-lh≤≤M|y<|aQ[=<nD→<⎇≤[~<m∧_(≠,≡_zλ,=≥y,]H≥~
}y(≥L≡Z88ML<h_-lλ_{m↑≠{Y-n≤h≠ld≠⎇<AQY_=∀_X<lT≠xZL\⎇H
M→(≥L≥≥9(∞,=≥<Ml9λ_O∀	,{,≡_z	&∀≥z;
D→:=
<Hβ!.Y<≤L↑y;]∧∧≥~→$<|{l=8=~-⎇\h_N];≥λ∞↑λ≥≠d
8=_m∧≥~→${{\nL;]λ∞=≥→.-H≥≠d∞~→#!,>≤≤L↑|z;meλ≠|D∞~→(∞l;≥9$∞Y=≥.-Y9λ∞⎇;≠λ∧
;Y~,<=→(l:;≥.,(~9AQ[[h
\=_z∧
<h≤
}|z8ML+Hβ!!"T_.N→<[N4≥z;
D_Y(∞,<≤Y.<;]→,D_<h
M<⎇≤d∧≥z=
∧_=≠m↑h≤Y.∞Y<y-n~;Yd{{\nL;]≤eA"X;LD≥X<M≤8[→.4≤Y<∞,<y;NL9λ_.4≠≠⎇l↑K8x.<(→|L\:h≠↑≥→<N5C"UlT≥z;
D≤Y<∞,<y;ND→X:-N<Y(/(≤Y.N<[Z-lh≥~T_=≠mT	,sIt,+H↓QR;H∞M→(_l≡y(≥
=λ_$
8=_m∧~<h∞
||z,-→+λ∞|(≥z-Mλλ≤L↑≥<[D(≠~.>λ≠yD↓"\_-≡\kλ∞⎇→<Y$88z∧∞_:<D
<h_$∞X<Z,≤[→(≥Yλ~.Nh≠8.Lz~;Lt_{{N>_;]¬a"KQj)u4∞aQKPQ(y3HλKM(DλtSu*πpq3JH4R5↓QQ[|D>_;.
→.I&;{8==⊗j⊂$¬⊂H⊂e∃.j⊂$¬⊂H	&|),j%≠(∂(¬¬	-x$Vh⊂j%⊃"KQ*⊗*LE↔c"W
\=_z5⊂(⊂Dλj.jλ∀	-x$Vh	-l$,j7$π(

∧Vx),dλJ(
∧VxI,dλj*#!+≠8==⊗j⊂$λH⊂j'5⊂(⊂d∧-xI&57(∂$	Sc"Eh3Qβ!%Q3Q∧∧V⊗FTC"KJ
.β!%P4⊂**β"C!%QtSjZ∞c"EhTβ"J=≥→.-H≠8.Lz~;Lt_x;DY8{m\(≤=-≡→(_m⎇<≠→/¬H⊃[n$→>_-↑≠→.AQKPQ(y3HλKMλDλtSu*πpq3JH4R5↓QI,wm\=_z5⊂(
λ$⊂j(¬λλ⊂j%↔j⊂(¬λH	-l∀,j(¬∧-xI&4⊂j*+T∂(
¬∧-x)&4⊂j(¬∧-xI&4⊃
*!QKQ4&∃,J!QW	,m\=_z5⊂(
λ$⊂j(¬λλ⊂j%↔j⊂(¬λH	-l∀,j(¬∧-x)&4⊂j*+T∂(∪Iq"KQ)hβ"KJ
.β!%Q3Q∧∧V⊗FDC"KHjβ"U
(≤y,={Yλ←_;<
L(→X-≥≤h≤m≥Xy#!-{Xy$∞y(~≡Y(_.>{xz,≡→9λ∧Vpi,$∞z=~∧∧-x)&∀≥y(
↑<⎇λ∞↑y(≥
=λ_.>{xz,≡~;{AQ]~≤M}9z≠n↑λ≥~T≤Y<nD≠yH∞M→(≤≡≥→<Md≠8==∞h_-lλ	,eλλpj$V(→≠l↑h≠[nD≠8==β"I&5	-x$Vhpj$V(≥z]H	-l∀,(→][⎇→.4	,pdV%@5

<h_.>⎇;9.4β"]
=λ≥
(≠8.Lzλ≤∞-xy9,Nh~;D(≠→,n=≠e↑Z9z∞D≠|Y↑KWkAQKP4λ~Uβ"J|(≥z-Mλ≥|M≡→(	&=8=_m∧,(~-d≥→<M↑h≠yD(≤⎇,,];XnM;{H
l;99∧∧,{8.Lz	.$t,+C!*~~<d∞⎇8YN]X⎇~-⎇H_x..Z9<d(≥~
≡Yλ_.,⎇;9-nλ	&=;~<nD,+λ∞⎇~8z∧∞Y<≤L↑y;]∞4≥~→!Q[~<nD≠yH↓Q\_<NM8;λ
\=_z↑kH∃m;Y=L↑H≥y$
≠xx.L(_(∞l<Z8,-→(~-d≥~→$>≤≤L↑|z;meλ≥y!QY>_-];Y(∞M→(_n↑\Y;ND	,{-M<⎇	&∃H∩9D∞~→(∞l<Z8,-→(_.∞→8<N5λ≥~]H≥y$
=<⎇∧z→8m1"Z=∞4→;]∞/(_9l≥;\⎇∧∞~→(=|\Y.>≠{Y
≥Yh≤≡]λ≠ld≥~→$∞_=≥↑[KH	≤H≥~T≥X<M≤8[→!QY≠y.4≠[⎇∧
xx⎇.$~;H∧V{;~.>	,+∧∞~→;D∞y(_.>{xz,≡→(≥
(≥X.-88[T≥z=
∧β"]
(_<∞∞[|≤M≤=→(∞<]λ
|H≥~T_{{N>_;]∧∞_=≥↑[KC!%PQ1i→H∀q)H0uλε7qtSjZ∞u⊂()5Jε'+
E↔c"KJεLN.AQKT∃ε&β"[,≡_z⊗n=∞y/∞↔(∂πT≠8==	.)dVv|_.Gy>≤π5λ
7!QKT∃ε↔β"[,≡_z	'∀i,vn=∞y/∞∞{;
≡⎇↔(πG(↔⊗l↑=8;=;~<nGsSw$β(∪Sg1"Wλ
≡x{{N>⊗|_.K(ε(>x;9,={\⎇>_=∞l←≤↔(β∀	9=∧Vnh	,↑	,hβ∀∪Sw'1"Wλ
≡⎇X<K>_=↔$β(_z\zv|≡∞y>∞π{≠{m><⊗|≡∞{;
≡⎇↔.m]~<⎇Wc"W∧∧9=	&4ε(≠,≡_z	'∀i,vkN⎇9YM∨⊗|_.K.c"KK≤⎇9Lm>⊗y/∞↔.c!+↔≠8.Lz	.$t,v|∞,9Z>>_=↔'>≤Y9M∨⊗y>∞.{;
≡⎇↔7!QKQ3HA"C"EhQ1r)d∀q3λXuλg8tSu*πu⊂0I~*f¬.c"Ej∃.↓QXz→,=v⎇X.'y>≤π>X;∞m]~<⎇T∂∂(;≠[⎇>X;↔$β(_{mlx=⊗m]y;]>X<Nl←≤↔.m]~<⎇Wc"W∞<;98m⎇\⎇⊗l←≤∞⎇L≥↔(ε$
;~<nGc"W∧\=	,dβ(∪SkQ"KQ)hβ"C!%PQ1i→H∀q)H0uλε7h⊃tIz4∞uλ_R5%ε.
.aQKT∃ε↔β"[
⎇z⎇<>X<NmK(∂∂+K{];
K{↔(β∀	,yDVnc"KD≤x;,↑X<Vnl<N{L≥96yM≡\⎇⊗mK77(β∀≥X;<Z<\nK{↔7'1"Wλ∧\=	,dβ(≠≠m⎇⎇<⊗nl<N|L↑⎇⊗{[7#"Eh3Qβ!%T∃FA"KQJ↓"U≠d{{<
L=→(
}<H→↑x|Z.∞~;{D
yH	&=8=_m∧,(≥lT≤z≠n]→λ≤n↑≤≠≡$∞~→(L=_(∞>≤]8nN<Y#!-8;Z.∞;_=
≥Yh→N]X⎇~-⎇\nH∧Vz<xm⎇\⎇	&∃λ	,m≡⎇X<DV+λ	&>≤Y9M∨	,+∧∧,|⎇,lZ>	&∃λβ"DV|x;,↑X<I&∃λ_;LD	,|l≥98{mn⎇	,'1"X;LD	,{-<;]	&∃λ	,ml;9)&∃λ_;LD	,⎇L≥	,+D
~→(m<\u∧Z=Y$<Y(∞,;_=\λ→\;~;Lt≥z=
↓"]~T≤Y<∞,<y;NL=~;md≠yH∞=≥→.-\nh∞M→(→M≥X;λ∞M≤Y9$
;][mNY(≥
(≤Y.∞Y<q-n_=~-⎇C"[ld≥~→$
h list. Note that we %6have%1 assumed that %3mlist%1 is a list.
We will restrict the match algorithm to simple matches on tree structure.
We represent %3prefix%1 as %3first%1 and %3suffix%1 and %3rest%1; much 
more general interpretations are possible.
We leave it to the reader  to supply representations of the missing functions.

Given a basic pattern matcher, we can begin to elaborate on a
data base management system. We need some means of controlling the matcher.
If several entries in the system match the inquiry, then we must decide how to
manage the matches. In simple cases we could  make a list of all the possibilities.
If the number of matches is very large we might want to  return a few
at a time, remembering where we were in the search of the base.
The natural extension of this idea
is to allow a potentially infinite set of elements present in the data base. 
In programming languages we are able to talk about such potentialities by
using a procedure.

Instead of having objects explicitly
stored in the base, we may allow procedures to occur as data base elements.
Such a procedure would generate elements. For example, instead of storing 
the integers as explicit objects, we could store a procedure to generate
the integers. This introduces two problems: how do we store procedures as
data objects;  and, assuming that we have called such a procedure and
it has delivered an explicit object, how do we represent the
notion that the %6next%1 time we call that procedure, we want the
%6next%1 object?  That is, a procedure named %3get_next_integer%1
should return %31%1 the first time it is called, but know to return
%32%1 the next time it is called in the same context.
It must also know to return %31%1 when it is called in a new context.

Other possible extensions involve the operations on the base.
Assume that
we know that "all roses are red" and we know that object O%41%1 is
a rose; if we ask the data base for all red objects, we should expect
to see O%41%1 appear as a candidate. That expectation requires
a deductive ability built into the base manipulator. That is, we need not have
explicitly stored the information in the base, buT we expect to be able to
deduce facts from information in the base using some relationships
and reasoning ability.

There are at least two ways the "rosas are red" pRoblem can be solved.
Notice that "all roses are red" is much like a procedure; given an
object which is a rose, it generates an object which is red. So,
on entering a rose object in the data base, the system could
also explicitly add the fact that the rose was red. This is an example
of an %2input demon%1. A demon is a procedure which is not explicitly called
but is activated by the occurrence of another event.
Whenever an object is added to the base the collection of input demons
is checked. If an applicable demon is found, it is activated; its activation
might activate other demons. 

The activation of a demon is a different kind of procedure call than
previously seen. The activation is done on pattern matching 
rather than by a user-initiated call.
Thus  the calling style is generally known as 
%2⊗→pattern directed invocation↔←%*#(⊗↑[Hew#72]↑,#⊗↑[Bau#72]↑).
The demon procedure is stored in the data base along with a pattern
which determines conditions for its activation. In the case of an input
demon, an input to the base initiates a match of the input demon patterns
against the input. If a match is found, the corresponding procedure(s)
is(are) executed.
The match process can bind  variables to parts of patterns and therefore the
procedure 
typically has access to the match information.

.GROUP;
Let's establish some notation and give an example.
To introduce records to our system we use a unary procedure named %3add_item%1.
The argument to %3add_item%1 is the record we wish to add.

.BEGIN CENTER;
.BOXA
%3add_item[(ROSE O1)]%1
.BOXB
.END

We will use a ternary procedure named %3add_demon%1 to insert demons
in the base. The first argument is the type of demon; so far we  have
discussed demons invoked by adding elements; we will also
have demons which are applied when items are removed, or when items are
accessed. These three types will be named %3ADD%1, %3REMOVE%1, and %3FETCH%1.
The second argument is the pattern which will invoke this demon; and
the third argument is the action to be taken if the pattern matches.
For example:

.BEGIN CENTER;
.BOXA
%3add_demon[ADD;(ROSE %7a%3);add_item[(RED %7a%3))]]%1
.BOXB
.END


.APART
.FP
Demons are also used to monitor the removal of information from the base.

The third use of demons is involved with another possible solution to the
"all roses are red" problem.
Instead of explicitly adding the fact that %3O1%1 is a red object
we might wait until a request for red objects occurs. At that time
we could use the "all roses are red" demon %6backwards%1.
That is, we could look for any roses in the  data base; the assertion
that and rose object is also a red object allows us to accept
rose objects as solutions to our inquiry.
This feature introduces a certain deductive capability to our system.
It also introduces some organizational problems.

We have to   recognize when a procedure is capable
of producing objects of the desired type. We therefore
index these data base procedures by a pattern which tells what
the procedure accomplishes. That pattern is called the procedure's goal
and the invocation of such a procedure is again pattern-directed, but
has an added connotation of being %2goal-oriented%1.

.GROUP;
Again, we introduce some notation and an example. Let the request
for a data base item be given by:
.BEGIN CENTER;SELECT 3;
.BOXA
%3fetch[%7a%3]%1, where %7a%1 is a pattern.
.BOXB
.END
.FP
Since a  %3fetch%1 request might discover several possibilities,
some being items  and some being goal-directed procedures, we 
need a way of examining the selected information.

We introduce a  function named %3try_next%1, whose single
argument is the result of a %3fetch%1. Each call on %3try_next%1
either produces a new item or signals that no more items exist
on the fetch list. 

.APART
An extension to this basic data base manipulating system has become 
convenient in artificial intelligence research. Let us assume we wish to
derive a plan or scheme for achieving a desired goal. In the 
derivation process we will make hypotheses and then pursue
their implications. A similar  behavior can be simulated if we allow
the creation of multiple data bases. Each base corresponds to a
hypothetical situation or world, and the  %3fetch%1-ing of
an object in a world corresponds to asking whether or not a 
desired state is attainable in that world. 

Instead of requiring that
all transformations occur in one data base, several systems 
(⊗↑[Con#73]↑, ⊗↑[QA4#72]↑) have implemented a layered data base.
In this situation we are able to add, delete and fetch from specified
data bases. We add two operations %3push_base%1 and %3pop_base%1
which allow us to  manipulate whole data bases as objects.

The control structures necessary for handling such data base manipulations 
are non-recursIve and will be discussed in {yonss(P222)}.
We will discuss some details of the data structure implementation  
in {yonss(P128)}.
For more information see ⊗↑[McD#75]↑ and ⊗↑[Con#73]↑.

.CENT(Problems)
.PT24
.NL
1.##Recall our discussion of %3match%1 on {yon(P229)}. 
Supply a representation for match lists and supply the eight
data structure functions.
.NL
2.##The %3match%1 routine we developed on {yon(P229)} required that %3pat%1
be a constant pattern. Write a more general pattern matcher named
%3unify%1 which allows either %3pat%1 or %3exp%1 to contain variables.
This more gereral match routine is called a unifier (⊗↑[Rob#65]↑).
.GROUP;
.PT2
For example:
.EQ
%3unify[(A (B %7a%3) A); (A (%7b%3 D) %7d%3)] = ((%7a%3  D)(%7b%3 B) (%7d%3 A))%1
.EQ1(13)
%3
\unify[(A (B %7a%3) A); (A (%7b%3 D) %7b%3)] = NO
\unify[(%7a%3 A  %7a%3); (%7b%3 %7b%3 B)] = NO
.END
.<<ABOVE "END" CLOSES EQ1>>
.APART
.SS(Algebra of Polynomials,,P264:)
.BEGIN TURN ON "#";
.FP
%1
Assume that we want to perform addition and multiplication
of polynomials and assume that each polynomial is of the
form %3p%41%* + p%42%* + ... + p%4n%1 where each 
term, %3p%4i%1, is a product of variables
and constants.  
The two components of each term are a constant part called the coefficient,
and the variable part.
We shall assume without loss of generality that the 
set of variables which appear in the polynomials are lexicographically
ordered, e.g.#%3x#<#y#<#z%1;  and assume that each variable part 
obeys that ordering; thus we would insist that %3xzy%82%1 be written %3xy%82%3z%1.
We do not assume that the terms are ordered within the polynomial; thus
%3x#+#xy%1 and %3xy#+#x%1 are both acceptable.
We further assume that the variables of
each %3p%4i%1 are distinct and that no %3p%4i%1 has %30%* as its coefficient.
The standard algorithm for the addition of
%9S%8n%4i=1%3p%4i%1 with   %9S%8m%4j=1%3q%4j%1 indicates that
%3q%4j%1 can be combined with a %3p%4i%1 if the variable parts of these terms 
are identical.  In this
case the resulting term has the same variable part  but has a
coefficient equal to the sum of the coefficients of %3p%4i%1
and %3q%4j%1.
We will examine four representations of polynomials, before finally
writing any algorithms. To aid in the discussion we will use
the polynomial %3x%82%* - 2y - z%1 as our canonical example.

.CENT(First representation)
.FP
We could use the representation of the differentiation
example.  
This would result in our example assuming the form:

.BEGIN CENTERIT;SELECT 3;
.BOXA
←(PLUS (TIMES 1 (EXPT X 2)) (PLUS (TIMES -2 Y) (TIMES -1 Z)))
.BOXB
.END
.FP
The above conventions specify an unambiguous representation for our class
of polynomials. Strictly speaking we did not need to impose
the ordering on the set of variables. 
However, we need to impose some additional constraints before we
have data structures which are well-suited to the class of polynomial
algorithms we wish to represent.

.CENT(Second representation)
.FP
We are really only interested in testing the equality of the variable parts;
we will not be manipulating variable parts in any other way.
So we might simply represent the variable part as a list of pairs;
each pair contains a variable name and the corresponding value of the exponent.
Using our knowledge of the forms of polynomials and the class
of algorithms we wish to implement, we write
%9S %3p%4i%1 as:

.BEGIN CENTERIT;
.BOXA
←%3( (%1rep of %3p%41%*), (%1rep of %3p%42%*), ...)%1
.BOXB
.END
.FP
which would make our example look like:

.BEGIN CENTERIT;SELECT 3;
.BOXA
←((TIMES 1 ((X . 2))), (TIMES -2 ((Y . 1))), (TIMES -1 ((Z . 1))))
.BOXB
.END
.FP
This representation is sufficient and it does have the 
flexibility we need,  but it is still not terribly  satisfying.
  We are ignoring too much of the structure in our class of 
polynomials.

.CENT(Third representation)
.FP
We know that the occurrence of variables is 
ordered in each variable part; we can assume that we know the class of 
variables which
may appear in any polynomial. So instead of writing %3x%82%*y%83%*z%1
as

.BEGIN CENTERIT;
.BOXA
←%3((X . 2) (Y . 3) (Z . 1))%*,
.PT2
.FP
we could write:←%3(2 3 1)%*   
.FP
assuming %3x, y, z%* are the only variables.
.BOXB
.END
.FP
In a further simplification, notice that the  %3TIMES%* in the
representation is superfluous. We %6always%* multiply the coefficient by
the variable part. So we could simply %3concat%* the coefficient 
onto the front of the variable part representation.

.BEGIN NOFILL;TURN ON "\";TABS 30,45;GROUP;
.BOXA
Let's stop for some examples.
\%2term\representation
\%32xyz\(2 1 1 1)
.PT2
\2x%82%*z\(2 2 0 1)
.PT2
\4z%83%*\(4 0 0 3)
.END
.BOXB
.FP
Thus our canonical polynomial  would now be represented as:

.BEGIN CENTERIT;SELECT 3;
.BOXA
←((1 2 0 0) (-2 0 1 0) (-1 0 0 1))
.BOXB
.END
.FP
This representation is not too bad; the %3first%*-part of any
term is the coefficient; the %3rest%*-part is the variable part.
For example, the test for equality of variable parts is 
now simply a call on %3equal%*.

Let's start thinking about the structure of the main algorithm.

.CENT(Fourth representation)
.FP
The algorithm for the sum must compare terms. Finding similar terms, it will
generate an appropriate new term, otherwise it simply copies the terms.
When we pick a %3p%4i%1 from the first polynomial we would
like to find a corresponding %3q%4j%1 with the minimum amount of
searching.  
This can be accomplished if we can order the terms
in the polynomials. 
A natural ordering can be induced on  the terms  by
ordering  the numerical representation of the exponents.
For sake of argument, assume 
that a maximum of two digits will be needed to express
the exponent of any one variable. 
Thus the exponent of %3x%82%1 will be represented as %302%*, or 
the exponent of %3z%810%1 will be represented as %310%*. Combining this with our
ordered representation of variable parts, we arrive at:
.GROUP
.BEGIN NOFILL;TABS 30,45;TURN ON "\";
.BOXA
\%2term\representation
.SELECT 3;
\43x%82%*y%83%*z%84\%3(43, 020304)
.PT2
\2x%82%*z\%3(2, 020001)
.PT2
\4z%83%*\(4, 000003)
.END
.BOXB
.APART
%1

.GROUP;
.FP
Now we can order on the numeric representation of the variable
part of the term.  One more change of representation, which will
result in a simplification in storage requirements:

.BEGIN CENTERIT;
.BOXA
←represent %3 ax%8A%3y%8B%3z%8C%1 as %3(a . ABC) 
.BOXB
.END
.APART;
.GROUP;

.SELECT 1;
.FP
This gives our final representation:

.BEGIN CENTERIT;SELECT 3;
.BOXA
←((1 . 20000) (-2 . 100) (-1 . 1))
.BOXB
.END
.FP
Note that %320000 > 100 > 1%1.
.APART

Finally we will write the algorithm.  We will assume that
the polynomials are initially ordered and will write the 
algorithm so as to maintain that ordering.
Each term is a dotted pair of elements: the coefficient
and a representation of the variable part.

.P60:
As in the previous differentiation example, we should 
attempt to extract the algorithm
from the representation.
.GROUP
.FP
We shall define:
.BOXA
.BEGIN CENTERIT;
←%3coef[x] <= car[x]%1 and %3 expo[x] <= cdr[x] 
.END
%1
.BOXB
.FP
To test the ordering we will use the LISP predicate:
.BOXA
.BEGIN CENTERIT;
←%3greaterp[x;y] %1gives %et%1 if %3x%1 is greater than %3y%1.
.END
%1
.BOXB
.APART
.FP
In the construction of the `sum'
polynomial we will generate new terms by combining coefficients.
So a constructor named %3node%* is needed.
In terms of the latest representation %3node%* is defined as:
.BOXA
.BEGIN CENTERIT;
←%3node[x;y] <= cons[x;y]%1
.END
.BOXB
.GROUP
.FP
So here's a graphical representation of our example polynomial:
.BOXA
.BEGIN CENTERIT
←%3x%82%* - 2y - z %1
.END
.BOXB
%3
.BEGIN NOFILL;
.BEGIN SELECT g;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#";
.TURN ON "∞" FOR "%";
.KRK
			    /\ 
			   /  \
			  /    \
			 /      \
			/\       \
		       /  \      /\
		      1  20000  /  \
			       /    \
			      /\     \
			     /  \     \
			   -2   100   /\
				     /  \
				    /   ∞3NIL∞*
				   /\
				  /  \
				 -1   1
.END
.APART
.GROUP
%1
.FP
Here's the algorithm:
%3
.BEGIN NOFILL;TABS 12,25,30,52,56;TURN ON "\";
.KRK
.BOXA
polyadd[p;q] <=
\[null[p] → q; 
\ null[q] → p;
\ greaterp[expo[first[p]];expo[first[q]]] → concat[\first[p];
\\\\\polyadd[rest[p];q]];
\ lessp[expo[first[p]];expo[first[q]]] → concat[\first[q];
\\\\polyadd[p;rest[q]]];
\ zerop[plus[coef[first[p]];coef[first[q]]]] → polyadd[rest[p];rest[q]];
\ %et%* → concat[\node[\plus[coef[first[p]];coef[first[q]]];
\\\expo[first[p]]];
\\polyadd[rest[p];rest[q]]]] 
.BOXB
.END

.BEGIN CENTERIT;

%1where:%3←←zerop[x]  <= eq[x;0]
.END
%1
.APART
.FP
.GROUP
Now for an explanation and example.
%1
.P72:

.BEGIN FILL;
.FP
%3polyadd%* is of the form: %3[p%41%* → e%41%*; p%42%* → e%42%*; 
p%43%* → e%43%*; p%44%* → e%44%*; 
p%45%* → e%45%*; p%46%* → e%46%*]
.END
.APART;

.GROUP;
.BEGIN SELECT 1;INDENT 0,10;FILL;
%3p%41%3 → e%41%1 and %3p%42%* → e%42%1 check if either polynomial is empty.
.PT2
.FP
%3p%43%* → e%43%1 and %3p%44%* → e%44%1. These clauses worry about the ordering of
terms so that the resultant polynomial retains the ordering.
.PT2
.FP
Otherwise the variable parts are equal.
.PT2
.FP
%3p%45%* → e%45%1.  If the variable parts are equal then we can  combine
terms.  However, we must check for cancellations and not include any 
 terms with zero coefficient in our resultant polynomial.
.PT2
.FP
%3p%46%1 → %3p%46%1.  In the final case we must add a new node to our polynomial.
.END
.APART;
%1
.GROUP
.FP
Here's an informal execution of %3polyadd:

.BEGIN NOFILL;TABS 10;TURN ON "\";
.KRK
.BOXA
.SELECT 3;
polyadd[x+y+z;x%82%*-2y-z]
\= concat[x%82%*;polyadd[x+y+z;-2y-z]]
\= concat[x%82%*;concat[x;polyadd[y+z;-2y-z]]]
\= concat[x%82%*;concat[x;concat[node[1+-2;y];polyadd[z;-z]]]]
\= concat[x%82%*;concat[x;concat[-y;polyadd[z;-z]]]]
\= concat[x%82%*;concat[x;concat[-y;polyadd[( );( )]]]]
\= concat[x%82%*;concat[x;concat[-y;( )]]]
.BEGIN CENTERIT;
←= x%82%*+x-y
.BOXB
.END
.END
.APART
.END
.END
.FP
Extensive work has been done on  polynomial manipulating algorithms
for efficient storage  and fast  execution (⊗↑[Got#76]↑).
.CENT(Problem)
.NL
1.##Write an algorithm, %3polymult%1, to perform the multiplication
of two polynomials.
.SS(Evaluation of Polynomials,,P2:)
.BEGIN TURN ON "←";
.FP
Though you are undoubtedly quite tired of looking at polynomials, there is
at least one more operation which iq usefully performed on polynomials.
The opepation is evaluation.
Given an arbitrary polynomial, and values for any of the variables which it
contains, we would Like to compute its value. First we will
assume that  the substitutions of values for variables has already been
carried out. Thuq we are dealing wiTh polynomials of the form: %9S%8n%4i=1%3p%4i%1
where %3p%4i%1 is a product of powers of constants. For example:
.BOXA
←%32%83%* + 3*4%82%* + 5%1. 
.BOXB
.FP
This could be represented as:
.BOXA
←%3(PLUS (EXPT 2 3) (PLUS (TIMES 3 (EXPT 4 2)) 5)).%*
.BOXB
.FP
We have taken this general representation because we have great expectations
of generalizing the resulting algorithm.

We will now describe a LISP function, %3value%*, which will take such an
S-expr representation and compute its value. Input to %3value%* will be
numerals or lists beginning with either %3PLUS, TIMES,%* or %3EXPT%*.
The value of a numeral is that numeral; to evaluate the other forms of input
we should perform the operation represented. We must therefore assume
that operations of addition, multiplication, and exponentiation exist.  
Assume they are
named +, *, and ↑, respectively. What then should be the value of a representation
of a sum?
It should be the result of adding the value of the representations of the
two summands or operands. That is, %3value%* is  recursive.
It should now be clear how to write %3value%*:

.BEGIN TABIT1(14);SELECT 3;
.BOXA
value[x] <=\[isconstant[x] → x;
\ issum[x] → +[value[arg%41%*[x]];value[arg%42%*[x]]];
\ isprod[x] → *[value[arg%41%*[x]];value[arg%42%*[x]]];
\ isexpt[x] → ↑[value[arg%41%*[x]];value[arg%42%*[x]]]]
.END
.PT18
.BEGIN  "XX26" GROUP;CENTERIT;SELECP 3;
%1where:%3←isconstant[x] <= numberp[x]
.EQ1(20)
\issum[x] <= eq[first[x];PLUS]
\isprod[x] <= eq[first[x];TIMES]
\isexpt[x] <= eq[first[x];EXPT]
.BOXB
.END
.END "XX26"
.<<PROBLEMS ON POLY EVAL >>
.SELECT 1;
.CENT(Problems)
.PT24
.NL
1.##Show how to extend %3 value%* to handle binary and unary minus.
.NL
2.##Write an algorithm  %3instantiate%*  which will take two arguments,
one representing a set of variables and values, the other representing
a polynomial. The algorithm is to return a representation of the
polynomial which would result from substituting the values for the variables.
.NL
3.##It would be nice if we could represent  expressions like 2+3+4 as
%3(PLUS#2#3#4)%* rather than %3(PLUS#(PLUS#2#3)#4)%* or %3(PLUS#2#(PLUS#3#4))%*;
or represent 2*3*4+5+6 as %3(PLUS#(TIMES#2#3#4)#5#6)%*.
Write a new version of %3value%* which can evaluate  such n-ary representations
of + and *.

.CENT(More on polynomial evaluation)
.FP
Though it should be clear that the current %3value%* function does perform
the appropriate calculation, it should be equally clear that the class of
expressions which %3value%* handles is not particularly powerful.
We might wish to evaluate  requests like:

.BEGIN tabit1(15);
.P122:
.BOXA
%2A%*\"What is the value of %3x*y + 2*z%* when %3x=4, y=2,%1 and %3z=1%*?"
.END
.BOXB
.P266:
.FP
Now the function %3instantiate%*, requested in problem 2  above, offers
one solution: make a new copy of the representation of %3x*y#+#2*z%*
with the variables physically replaced by their 
values⊗↓We have seen this substitution and simplification process before in
discussing %3equal%1 on {yon(P1)}.
It is a minimal but useful model for computation.←. This would result
in a representation of %34*2#+2*1%*, and this new expression is suitable
fare for %3value%*. Computationally, this is a terrible solution.
%3instantiate%* will go through the structure of the expression looking
for instances of variables, and when located, will replace them with
the  appropriate values. %3value%* then goes through the structure of
the resulting expression performing the evaluation. We desire
 a function, %3value%9'%1, which combines the two processes: 
the basic structure of %3value%9'%1 is that of mild-mannered %3value%*,
but when a variable, say %3x%*, is recognized inside %3value%9'%1 then %3value%9'%1
would look at a table like that expected by %3instantiate%*, find %3x%*
and return the value associated with the entry for %3x%*.

.BEGIN TURN OFF "{","}";TURN ON "#";
Let's formalize our intuitions about %3value%9'%1. 
It will be a function of two arguments. The first will be a
representation of a polynomial; the second will be a representation of
the table of variables and values. 
You may have noticed that the original version of %3value%*
%6does%1 handle expressions which are not actually constant
polynomials; %3(2#+#3)*4%* for example. Since we will wish to
apply our evaluation functions to more general classes of expressions
we will continue, indeed encourage, this generality.
Regardless of the class of expressions we wish to examine, it is
the structure of the table which should be the first order of business.
An appropriate table, %3tbl%*, will be a set of ordered pairs  
%3<name%4i%*,#val%4i%*>%1;
thus for the above example the table %3{<x,#4>,#<y,#2>,#<z,#1>}%1 would suffice.
Following our dictum of abstraction and representation-independent programming,
we will not worry about the representational problems of such tables. We will
simply assume that "tables" are instances of an abstract data structure  
called %d<table>%*, and we will only
concern ourselves for the moment with the kinds of operations we need
to perform. We will need two selector functions: %3name%*, to select
the variable-component of a table entry; and  %3val%*, to select the
value-component. A complete discussion of such a data structure would
entail discussion of constructors and recognizers, and perhaps other
functions, but for the current %3value%9'%1, these two functions will suffice.

%3value%9'%1 will need a table-function, %3locate%*, to locate an appropriate
variable-value entry. The binary function
%3locate%* will take an  argument, %3x%*, 
representing a variable;
and an  argument, %3tbl%*, representing a table. 
%3locate%* will match %3x%* against the
%3name%*-part of each element in %3tbl%*; 
if a match is found then the corresponding
%3val%*-part is returned. If no match is found then %3locate%* is undefined.

So far, little structure has been imposed on elements of %d<table>%*;
tables are either empty or not; but if a table is non-empty then each
element is a pair with recognizable components of %3name%1 and %3val%1.
However, the specification of  algorithms to examine
elements of %d<table>%* imposes more structure on our tables.
If we were dealing with 
mathematical functions 
rather than algorithms then a side condition to the effect
that a table had no pairs with duplicate first elements would be sufficient
(and required).
However, we are dealing with algorithms and therefore  must describe a method for
locating elements. 

Recursion is the only method we have for  specifying
%3locate%*, and recursion operates by decomposing a structure. Sets are
notorious for their lack of structure; there is no order to the elements of a
set. But if we are to write a LISP algorithm for %3locate%*, that algorithm will
have to be recursive on the "structure" of %3tbl%*,
and so we impose an ordering on the elements of that
table. That is, we will represent tables as %6sequences%*. We know
how to represent sequences in LISP: we use lists.
.END
.BEGIN GROUP;TURN ON "{","}";
With this introduction, here's %3locate%*⊗↓The  interpretation
of %3tbl%* as a function implies that %3locate%* represents function application;
i.e., %3locate[x;tbl]#%1is%*#tbl(x)%*.This is a very acceptable interpretation
of table lookup.←:
.BEGIN TABIT1(19);SELECT 3;GROUP;
.P123:
.BOXA
locate[x;tbl] <=\[eq[name[first[tbl]];x] → val[first[tbl]];
\ %et%* → locate[x;rest[tbl]] ]
.BOXB
.END
.END
.FP
The effect of %3locate%1 is to find the %6first%1 element of %3tbl%1 which
has a %3name%1-component which matches %3x%1.  Having found that
match, the corresponding %3val%1-part is returned. If there were other
matches further along in the sequence %3locate%1 would not see them.
Other representations of tables are certainly possible. This representation
will be useful in later applications.

.BEGIN TABIT2(20,36);GROUP;
And here's the new more powerful %3value%9'%1:
.BOXA
.SELECT 3;
value%9'%*[x;tbl] <=\[isconstant[x] → x;
\ isvar[x] → locate[x;tbl];
\ issum[x] → +[\value%9'%*[arg%41%*[x];tbl];
\\value%9'%*[arg%42%*[x];tbl]];
\ isprod[x] → *[\value%9'%*[arg%41%*[x];tbl];
\\value%9'%*[arg%42%*[x];tbl]];
\ isexpt[x] → ↑[\value%9'%*[arg%41%*[x];tbl];
\\value%9'%*[arg%42%*[x];tbl]] ]
.BOXB
.END
.FP
Notice that %3tbl%* is carried through  as an explicit argument to 
%3value%9'%1 even though it is only accessed when a variable is recognized.
Notice too that much of the structure of %3value%9'%1 is quite repetitious;
the lines which handle sums, products, and exponentiation are identical
except for the function which finally gets applied to the evaluated arguments.
That is, the basic structure of %3value%9'%1 is potentially of broader application
than just the simple class of polynomials.
In keeping with our search for generality, let's pursue %3value%9'%1 a little
further.

What %3value%9'%1 says is:
.PT24
.NL
%21.%*##The value of a constant is that constant.
.NL
%22.%*##The value of a variable is the current value associated with 
that variable in the table.
.NL
%23.%*##The value of a function call is the result of
applying the function to the evaluated arguments. It just turns out
that the only functions %3value%9'%1 knows about are binary sums, products,
and exponentiation.
.PT24
.GROUP
Let's clean up %3value%9'%1 a bit.

.BEGIN TABIT2(18,44);SELECT 3;GROUP;
.BOXA
value%9'%*[x;tbl] <=\[isconstant[x] → x;
\ isvar[x] → locate[x;tbl];
\ isfun_args[x] → apply[\fun[x];
\\eval_args[args[x];tbl]
\ %et%3 → %9B%3]
.BOXB
.END
.APART
.FP
The changes are in the third branch of the conditional. We have a new
recognizer, %3isfun_args%* to recognize
function application. We have two new selector functions; %3fun%*
selects the representation of the function --#sum, product, or power
in the simple case; %3args%* selects the arguments or parameters to the
function --#in this case all functions are binary. We have two
new functions to define: %3eval_args%*, which is supposed to evaluate
the arguments finding  values for any of the variables; 
and %3apply%*, which is used to perform the desired operation on the evaluated
arguments.

.BEGIN TURN OFF "}","{"; TURN ON "#";
We are still trying to remain as representation-free as possible: thus
the generalization of the algorithm %3value%9'%1, and thus the care
in picking representations for the data structures.
We need to make another data structure decision now; when writing the 
function %3eval_args%*, we will be giving a recursive algorithm.
This algorithm will be recursive on the structure of the first argument,
which is a representation of the arguments to the function. In contrast
to our position when writing the function %3locate%*, there %6is%* a
natural structure on the arguments to a function: they form a 
sequence. That is %3f[1;2;3]%* is typically not the same as %3f[3;2;1]%*
or %3f%1 applied to any other permutation of {1,#2,#3}. 
Thus writing %3eval_args%* as a function,
recursive on the sequence-structure of its first argument, is quite
natural. Here is %3eval_args%*:
.END
.BEGIN TABIT2(25,38);SELECT 3;GROUP;
.BOXA
eval_args[args;tbl] <=\[null[args] → ();
\ %et%* → concat[\value%9'%*[first[args];tbl];
\\eval_args[rest[args];tbl]] ]
.BOXB
.END
.FP
Notice that we have written %3eval_args%* without any bias toward binary
functions; it will evaluate a sequence of arbitrary length, returning a sequence
representing the evaluated arguments.

.GROUP;
There should be no real surprises in %3apply%*; it gets the representation
of the function name and the sequence of evaluated arguments and
does its job:

.BEGIN TABIT2(25,42);SELECT 3;GROUP;
.BOXA
apply[fn; evargs] <=\[issum[fn] → +[\arg%41%*[evargs];
\\arg%42%*[evargs]];
\ isprod[fn] → *[\arg%41%*[evargs];
\\arg%42%*[evargs]];
\ isexpt[fn] → ↑[\arg%41%*[evargs];
\\arg%42%*[evargs]] ]
.BOXB
.END
.APART
.FP
If we should desire to recognize more functions then we need only
modify %3apply%*. That would be a satisfactory short-term solution, but  we
 would like a more general
function-definition facility. Such a  feature would allow new functions to
be defined during a computation; then if an application of that function
were needed, the %3value%*-function would find that definition and
apply %6it%* in a manner analogous to the way the pre-defined functions are
applied. 
How far away are we from this more desirable  super-%3value%*?
Well %3value%9'%1 is already well-endowed with a mechanism for locating
values; perhaps we can exploit this judiciously placed code.
In what context would we be interested in locating function definitions?
Here's an example:

.BEGIN tabit1(15);
.P124:
.BOXA
%2B%*\"What is the value of %3f[4;2;1]%* when %3f[x;y;z] <= x*y + 2*z%*?"
.BOXB
.END
.FP
If we have a means of recovering the definition of %3f%*,
then we can reduce the problem to %2A%* of {yon(P122)}.
We will utilize the table-mechanism, and therefore will use %3locate%*
to retrieve the definition of the function %3f%*.
In our prior applications of %3locate%* we would find a constant
as the associated value. Now, given the name %3f%*, we would expect
to find the definition of the function.
The question then, is how do we represent the definition of %3f%*?
Certainly  the body of the function, %3x*y#+#2*z%*, is one of the
necessary ingredients, but is that all? Given the expression %3x*y#+#2*z%*
can we successfully compute %3f[4;2;1]%*?
Not yet; we need to know the correspondence between the values %31,#2,#4%*
and the variables, %3x, y, z%*. That information is present in our
notation %3f[x;y;z]#<=#...%*, and is a crucial part of the definition of %3f%*.
That is, the %6order%* of the variables appearing after the function name
is an integral part of the definition:
%3f[y;z;x]#<=#x*y#+2*z%* defines a different function.

Since we are now talking about %6representations%* of functions, we
are entering the realm of abstract data structures again. We have a
reasonable understanding now of the essential components of such a representation.
For our purposes, a function has three parts:

.BEGIN INDENT 10,10;
.PT24;NL
%21.%*##A name; %3f%* in the current example.
.NL
%22.%*##A formal parameter list; %3[x;y;z]%* here.
.NL
%23.%*##A body; %3x*y + 2*z%* in the example.
.END
.PT24
.FP
We do not need a complete study of representations for functions yet. For
our current discussions we can assume a representation exists, and that
we are supplied with three selectors to retrieve the components mentioned
above.
.PT24
.NL
%21.%*##%3name%* selects the name component from the representation. We have
actually seen %3name%* before in the definition %3locate%* on {yon(P123)}.
.NL
%22.%*##%3varlist%* selects the list of variables from the representation.
We have already seen that the natural way to think about this component
is as a sequence. Thus the name  %3varlist%*.
.NL
%23.%*##%3body%* selects the expression which is the content of the definition.
.PT24
.FP
Given a function represented in the table according to these conventions, how
do we use the information to effect the evaluation of something like 
%3f[4;2;1]%*?
First %3value%9'%1 will see the representation of %3f[4;2;1]%*;
it  should recognize this as an instance of function-application at the following
line of %3value%9'%1:
.BOXA
.BEGIN CENTERIT; SELECT 3;
←isfun_args[x] → apply[fun[x];eval_args[args[x];tbl]]
.BOXB
.END
.FP
This should cause an  evaluation of the arguments and then
pass on the work to %3apply%*.

Clever %3apply%* should soon realize that %3f%* is not the name of a 
known function. It should then extract the definition of %3f%* from the
table; associate the evaluated arguments (%34,#2,#1%*) with the variables 
of the parameter list (%3x,#y,#z%*), making a new table with name-value pairs
(%3<x,#4>,#<y,#2>,#<z,#1>%1).
Now we are back to the setting of problem %2A%* of {yon(P122)}.
We should ask %3value%9'%1 to evaluate the %3body%*-component
of the function using the new %3tbl%*.
This works fine for %3x%1, %3y%1, and %3z%1; within the evaluation of the body
of %3f%1 we will find the right bindings for these variables. But we might 
also need some information from the original %3tbl%1. The evaluation ob the
body of %3f%1 might entail the application of some function definition
present in %3tbl%1. For example, the representation of 

.BEGIN CENTERIT;
.P265:
.BOXA
←"what is %3g[2]%1 where %3g[x] <= x+s[x];%1 and %3s[x] <= x*x%1?"
.END
.BOXB
.FP
Within the body of %3g%1 we need the definition of %3s%1. Therefore,
instead of building a new table we will add the new bindings to the front of the
old table. Since %3locate%1 begins its search from the front of the table
we will be assured of finding the new bindings; since the old table is still
accessible we are assured of finding any necessary previous bindings.

We should be able to create a new %3value%9''%1 now.
Looking at the finer detail of %3value%9'%1 and %3apply%*,
we can see a few other modifications need to be made.
%3apply%9'%1 will        locate   the function
definition and thus %3tbl%* should be included as a third argument to 
%3apply%9'%1. That is, inside %3apply%9'%1 we will have:

.BEGIN CENTERIT;
.BOXA
←%3isfun[fn] → apply%9'%3[locate[fn;tbl];evargs;tbl]%1;
.END
.BOXB
.FP
After %3locate%1 has done its work,
this line (above) will invoke %3apply%9'%1 with a function definition as first
argument. We'd better prepare  %3apply%9'%1 for such an eventuality with the
following addition:
.BEGIN CENTERIT; SELECT 3;
.BOXA
←isdef[fn] → value%9''%*[body[fn];newtbl[varlist[fn];evargs;tbl]];
.END
.BOXB
.FP
What does this incredible line say? It says 
.BEGIN INDENT 7,7,7;
"Evaluate the body of the function using a new table manufactured from
the old table by adding the pairings of the elements of the formal parameter
list with the evaluated arguments."
.END
It also says we'd better write %3newtbl%*. This LISP function will make
a new table by adding new name-value pairs to an existing table.
So we'd better name a constructor
to generate a new name-value pair:
.DEF
%3mkent%* is the constructor to make new entries. It will take two arguments:
the first will be the name, the second will be the value.

Since we have assumed that the structure of tables, variable-lists, and
calling sequences to functions are %6all%* sequences, we will
write %3newtbl%* assuming this representation.

.BEGIN TABIT3(26,38,45);GROUP;SELECT 3;
.BOXA
newtbl[vars;vals;tbl] <=\[null[vars] → tbl;
\ %et%* → concat[\mkent[first[vars];first[vals]];
\\newtbl[\rest[vars];
\\\rest[vals];
\\\tbl]] ]
.END
.BOXB
.GROUP;
.FP
And finally here's the new %3value%9''%*-apply%9'%1 pair:
.P125:

.BEGIN TABIT2(20,46);SELECT 3;GROUP;
.BOXA
value%9''%*[x;tbl] <=\[isconstant[x] → x;
\ isvar[x] → locate[x;tbl];
\ isfun_args[x] → apply%9'%3[\fun[x];
\\eval_args[args[x];tbl];
\\tbl] ]
.BOXB
.END
.APART;
.BEGIN TABIT3(26,47,54);SELECT 3;GROUP;

apply%9'%3[fn;evargs;tbl] <=\[issum[fn] → +[arg%41%*[evargs];arg%42%*[evargs]];
\ isprod[fn] → *[arg%41%*[evargs];arg%42%*[evargs]];
\ isexpt[fn] → ↑[arg%41%*[evargs];arg%42%*[evargs]];
\ isfun[fn] → apply%9'%*[locate[fn;tbl];evargs;tbl];
\ isdef[fn] → value%9''%*[\body[fn];
\\newtbl[\varlist[fn];
\\\evargs;tbl]] ]
.END
.BEGIN TABIT2(25,37);SELECT 3;GROUP;

eval_args[args;tbl] <= \[null[args] → ( );
\ %et%* → concat[\value%9''%*[first[args];tbl]; 
\\eval_args[rest[args];tbl]] ]
.END
.BOXB
Let's go through a complete evaluation of %2B%* of {yon(P124)}.
As before, we will use %eR%* as a mapping from expressions to representations.
Thus we want to pursue: 
.BEGIN TURN ON "←";TURN OFF "{","}";
.BOXA
←%3value%9''%*[%eR%f(%3 f[4;2;1] %f)%*; %eR%f(%3{ <f, [[x;y;z] x*y + 2*z]> }%f)%3]%1.
.BOXB
.FP
Let us denote the initial symbol table, 
%eR%f(%3{#<f,#[[x;y;z]#x*y#+#2*z]>#}%f)%1 as %3init%1. This will simplify many 
of the expressions.
Notice that
our representation of %3f%* in %3init%1 has associated the variable list %3[x;y;z]%1
with the body of the function. Thus %3locate%1, operating on this table with the
name %3f%1, will return a representation of %3[[x;y;z]#x*y#+#2*z]%1.

.GROUP;
%3isfun_args%* should be satisfied and thus the computation should reduce to:
.BEGIN TABIT2(10,19);
.BOXA

\%3apply%9'%3[\fun[%eR%f(%3 f[4;2;1] %f)%3];
\\eval_args[args[%eR%f(%3 f[4;2;1] %f)%3];init];
\\init]%1
.BOXB
.END
 or:←%3apply%9'%3[
%eR%f(%3 f %f)%3
;eval_args[
%eR%f(%3 [4;2;1] %f)%3;
init];
init
]
.BOXB
.APART;
.GROUP;
.FP
%3eval_args%1  will build a sequence of the evaluated arguments: %3(4,#2,#1)%1,
resulting in:

←%3apply%9'%3[
%eR%f(%3 f %f)%3
;(4, 2, 1)
;
init
]
.APART;
.GROUP;
.BOXB
.FP
%3apply%9'%1 should decide that %3f%* satisfies %3isfun%* giving:
.BOXA
←%3apply%9'%*[
locate[
%eR%f(%3 f %f)%3
;
init
];
(4, 2, 1)
;
init
]%1
.BOXB
.APART;
.GROUP;

.FP
%3locate%* will  retrieve the definition, and

←%3apply%9'%*[
%eR%f(%3  [[x;y;z] x*y + 2*z] %f)%3
;
(4, 2, 1)
;
init
]%1 
.FP
should be the result.
.APART;
.GROUP;

Next, %3apply%9'%1 should realize that 
%eR%f(%3  [[x;y;z] x*y + 2*z] %f)%1 satisfies 
%3isdef%1  and thus:

.BOXA	
←%3value%9''%*[body[
%eR%f(%3  [[x;y;z] x*y + 2*z] %f)%3
];newtbl[varlist[
%eR%f(%3  [[x;y;z] x*y + 2*z] %f)%3
];(4,2,1);init]]%1
.BOXB
##or:←%3value%9''%*[
%eR%f(%3  [x*y + 2*z] %f)%3
;newtbl[
%eR%f(%3  [x;y;z]  %f)%3
;(4,2,1);init]]%1
.FP
after %3body%* and %3varlist%* are finished.
.APART;
.GROUP;
.FP
%eR%f(%3#[x;y;z]#%f)%1 is 
%3(%eR%f(%3#x#%f)%3,#%eR%f(%3#y#%f)%3,#%eR%f(%3#z#%f)%3)%1, 
and therefore the computation of
%3newtbl%*  will build a new table with entries for %3x,#y,#%1#and#%3z%1 on
the front:
.BOXA
←%eR%f(%3{ <x, 4>, <y, 2>, <z, 1>, <f, [[x;y;z] x*y + 2*z]> }%f)%1.
.BOXB
.APART;
.GROUP;
.FP
Thus we call %3value%9''%1 with:
.BOXA
←%3value%9''%*[
%eR%f(%3  [x*y + 2*z] %f)%3;
%eR%f(%3{ <x, 4>, <y, 2>, <z, 1>, <f, [[x;y;z] x*y + 2*z]> }%f)%3
]%1.
.BOXB

.APART;
.END
.FP
Now we're  back at problem %2A%* of {yon(P122)}.
.CENT(Time to take stock)
.FP
We have written a reasonably sophisticated algorithm here;
we should 
examine the results quite carefully.
Notice that we have written the algorithm with almost no
concern for representation. We %6assume%* that representations
are available for such varied things as arithmetic expressions,
tables, calls on functions, and even function definitions. Very
seldom did we commit ourselves to anything close to a concrete
representation, and then only with great reluctance. It was
with some sadness that we imposed a sequencing on elements of
tables.  
Variable lists and calling sequences were not as traumatic;
we claimed their natural structure was a sequence. As always,
if we wish to run these programs on a machine we must supply some
representations, but even then the representations will only
interface with our algorithms at the constructors, selectors and recognizers.

We have made some more serious representational decisions in
the structure of the algorithm.  We have encoded a version
of the %2CBV%*-scheme of {yon(P121)}. We have seen what kinds of
difficulties   that    can cause. We will spend a 
large amount of time in {yonsec(P113)} discussing the problems
of evaluation⊗↓A second decision was implied in our handling of function
definitions; namely we bound the function name to a structure consisting
of the formal  parameter list and the function body. This representation 
gives the expected result in most cases, but involves one of the
more problematic areas of programming languages: how do you
find the bindings of variables which do not appear in the current variable
list? Function names belong in this category. Such variables are called
non-local variables. The scheme proposed in this section finds the
binding which is current when the function was applied. Some programming
languages follow this; some other languages advocate 
finding the binding which was current
when the function was defined, and some languages allow both. 
The next two chapters begin a study of binding strategies.←.

.P186:
Finally, our decisions on the data structures and the algorithms were not
made independently. For example, there is strong interaction between 
our representation
of tables and the algorithms, %3locate%1 and %3newtbl%1 which  manipulate
those tables. We should ask how much of this interaction is inherent 
and how much is gratuitous. For example, we have remarked that our representation
can have pairs with duplicate first elements. It is the responsibility of %3locate%1
to see that we find the expected pair. If we wrote %3locate%1 to search from right
to left, we could get the wrong pair. 
We %6could%1 write %3newtbl%1 to be more selective; it could manufacture
a table without such duplications:

.BEGIN nofill; turn on "\";TABs 27,38,49 ;GROUP;SELECT 3;
.KRK
.BOXA
newtbl[vars;vals;tbl] <= \[null[tbl] → \[null[vars] → ();
\\ %et%3 → concat[\mkent[first[vars];first[vals]];
\\\newtbl[rest[vars];rest[vals];( )]]];
\ member[name[first[tbl]];vars] → newtbl[vars;vals;rest[tbl]];
\ %et%* → concat[first[tbl];newtbl[vars;vals;rest[tbl]]] ]
.END
.BOXB
.FP
This version of %3newtbl%1 requires much more computation than the alternative.
Its advantage is that the "set"-ness of symbol tables is  maintained. 
The "set" property is one which we need not depend on for our algorithms; in fact,
we will frequently expect that a table is represented as a sequence with
the previous values  of variables  found further along in the sequence.


The main point of this example however is to impress on you
the importance of writing at a sufficiently high level
of abstraction. We have produced a non-trivial algorithm
which is clear and concise. If it were desirable to 
have this algorithm running on a machine we could code it and
its associated data structure representations in a very short time.
In a very short time %6we%* will be able to run this algorithm
on a LISP machine.


.CENT(Problem)
.NL
%21.%1##On {yon(P266)} we mentioned the possibility of writing the new %3value%1
as a combination of old %3value%1 and %3instantiate%1. We rejected
that scheme. On {yon(P265)}  we had to save an old table since we might
need some previously defined functions. We might not have had this difficulty
if we had substituted directly. Write a substitution-type %3value%1 and
use it to evaluate the %3g[2]%1 example.
.<<AND THE GREAT MOTHERS>>
.REQUIRE "PROB6.PUB"SOURCE_FILE;
.SS(Another Respite)
.fp
We have again reached a point where a certain amount of reflection would be
beneficial.
Though this is not a programming manual we would be remiss if we did not
attempt to analyze the style which we have tried to exercise when writing
programs. 
.pt24
.NL
%21.%1##Write the algorithm in an abstract setting; do not muddle the abstract
algorithm with the chosen representation.  If you follow this dictum your
LISP programs will never use %3car, cdr, cons%1, and %3atom%*, and rarely use
%3eq%1.
All instances of these LISP primitives wi|l!be relegated to small subfunctions
which manipulate representations. 
.NL
%22.%1##When writing the abstract program, do not be afraid to  cast off
difficult parts of the implementation to subfunctions. Remember that if
you have trouble keeping the details in mind when %6writing%* the program,
then the confusion involved in %6reading%* the program at some later time
will be overwhelming. Once you have convinced yourself of the
correctness of the current composition, then worry about the construction
of the subfunctions. Seldom does the process of composing a program flow
so gently from top-level to specific representation. 
Only the toy programs are easy; the construction of the practical
program will be confusing, and will require much rethinking.
But bring as much structure as you can to the process.
.NL
%23.%1##From the other side of the question, don't be afraid to look at
specific implementations, or specific data-structure representations before
you begin to write. There is something quite comforting about a "real"
data structure. Essentially data structures are static objects
⊗↓At least within the program presently being constructed.←, while
programs are dynamic objects. A close look at a possible representation
may get you a starting point and as you write the program a distinction will
emerge between a dependence
on the specific representation and the use of
properties of an abstract data structure.
.PT24
Perhaps the more practical reader is overcome by the inefficiencies inherent
in these proposals. Two answers: first, "inefficiency" is a very ethereal concept.
Like "structured programming", it is difficult to define but recognizable
when it occurs.
Hardware development has enabled us to efficiently execute many operations
which were  quite inefficient on earlier machines.
But even at a more topical level, much of what seems inefficient can now be
straightened out by a compiler (see {yonsec(P107)}). 
Frequently, compilers can do very clever optimizations to generate efficient code.
It is better to leave the cleverness to the compiler, and the clarity to the 
programmer.

The current problems in programming are not those of efficiency; they are
problems of %6correctness%*. 
That is, we have a better grasp of techniques for improving efficiency of programs
than we do of techniques for gu@%IS]N↓iQJA
←]giIkGiS=\A←L↓ae←OIC[fA]QSGP4∃o←e,\~∃⊃=nAI↑↓s←jA]eSiJ↓BAae=OeCZ↓oQSG Ao←e-f}~∃U]iSX↓aeCGQSGCXAi←←1bACe∀AIKm∃Y←aK⊂AM←d↓ae←m%]NAG=eeKGQ]Kgf↓ShASLAk`~)i↑Ai!JAae=OeC[5KdAi<AGKeQSMrA!SfAaI←OeC5f\Aβ9rA[KQQ←I←1←OrA]QSGPAGC\4∃CSH↓iQJAAe←Oe¬[[Kd↓oSYX↓EJA[=ghAo∃YG←[∀\~∃π1KCeYdXAiQ∀AGY←MKdAs=jAGC8AoeSQJAiQ∀Aae←≥eCZAQ↑As←UdAS]QkSiS=\XAi!J~∃Y∃gfAG!C]GJ↓iQKe∀ASfA→←dAKIe←d\↓)QSf↓oCfA=]JA←_AiQJ↓eKCg=]fAM=dAIKYKY←a%]N~∃!SOP[1KmKX↓YC]OUCOKf8A)QJ↓←eSO%]CXA5←iSm¬iS←\↓M←d~)gkGP↓YC]OUCOKf↓oCfA∧AG←]YK]SK9hA]←QCiS←8AM←d↓Kqae∃ggS]≤A]k[∃eSGC0Aae←	YK[f8~∃/SQPAICQBAgiIkGikIKfXA]JACe∀ACEY∀Ai↑A→←e[C1SuJA∧AEe←¬IKdAIC]OJ↓←LAI=[CS]LX@~∃∃qaeKMgS]N↓←kdA%IKCf↓CfAI¬iBAgQekGiUeJA[¬]Sak1CiS←9fAeCQQKd~)iQC\↓CfA]U[KeS
CXAe∃YCiS=]gQSAf\~∀4∃)QKIJACe∀AChA1KCgh↓io↑@4∃WS]⊃fA←L↓Kee←IfAoQ%GPACIJAae∃mCYK9hAS\↓ICiB↓giek
ikeJ↓ae←OIC[[S9Nt~∀↓Kee←IfA←L↓←[SgMS←\F4ZG[SMk]IKIgiC]⊃S]NA=LAiQ∀AECg%FACY≥←eSi!ZvAC9H~∃KIe←ef↓←LAG=[[SgMS←\F4ZGKeI←efA⊃kJAi<A[Sg¬aaYS∃HAGY∃mKe]∃gfAS8ACii∃[aiS9N~∃i<AEJA∃MMSG%K]h\4∀~∃)!JA←G
keeK9GKfA=LAKeI←efA=LA←[%ggS←8AGC\↓EJA[%]S[SiKH~∃	r@AaIKgK]QS]NAQQJAkMKdAo%iP~∃Ae←Oe¬[[S]≤AG←]MiekGQfAoQ%GPACIJAGY=gJAi<AiQJ↓S]M←I[CXA¬YO←e%iQZ\4∃'kG AG←]MiekGQfAS]
YkIJ↓G←]iI←XAgQekGiUeKfX↓ICiB↓giek
ikeKLX~∃C9H@Ae∃aeKg∃]iCi%←]fA→←dA←AKeCi%←]f\4∀~∃Ie←ef↓←LAG=[[SgMS←\A
←[ae%gJ~∃QQJAOIKChA5CU←e%irA←_AiQJ↓aeKg∃]hAI¬rAQK¬ICGQ∃f\A∪PASfA!KeJAQQChAAe←Oe¬[[S]≤~∀JmMisYJ∀TAGC8AEJ@↓EK]K→SGSC0tAWK∃`AiQ∀AeKaIKgK]QCiS←8A←LAQQJAI¬iBAgQekGiUeKf@4∃CoCdAMe←4AiQJ↓IKgGISaiS=\A←L↓iQJ~)CYO←ISiQZlAoeSQJAG←9GSgJ↓CEgiICGhAAe←Oe¬[fXAACggS9NA←M_AeKgA←]gS	SYSi%KfAi<~∃gk	Mk]GQS←]f8A/QK9KmKd↓BAIK→S]Si%←\A←_@EgiIkGikIKHAaI←OeC5[S]NλASfA¬eeSm∃HACh0~∃iQ%fACIYSGJA=\Aae=OeC[5S]NAMisYJ↓oSYX↓]↑AI=kEhA	JAS]
YkIK⊂\~∀~)¬KM←IJAGY=gS]N↓iQSf↓ISgGUggS←8A←L@↓→∪' ↓ae←OIC[[S9NAgieYJXA]J~∃G¬\OhA!KY`A	khA]=iJAi!ChAS8AiQJ↓aeKG∃IS]N↓gKGi%←\X@∀e)QJ↓∂eKCPA≠←i!KefJ(AQCm∀~∃G←5aYKi∃YrAS≥]←eK⊂A←kd↓O←←H↓CImS
J\A)!SfAo=kYHA	JABA≥←←HAQS[JA→←dAi!J~∃S9iKeKMiKHAIKCIKHAi↑A¬Egie¬GhAi!J@JgQO[←C_JTAC1O←eSQQZAMI←ZAi!J~∃a¬eiSGUYCdA⊃CiBAIKaeKMK]iCQS←\\↓)QSf↓IKiK
iSmJ↓o←eV↓oSYX↓EJA[=gh~∃IKoCe⊃S]N\4∀~∀]
≥(QAe←EY∃[fR~(~∀b\↓/eSi∀AC\A¬Egie¬GhAm∃egS←8A←L@∀giO[=CLJT8~∀_\xyA%∨-∪9∞A!%=!%)%&||4∀]≥a(A!β≥
v~∀9'&Q!I←mS]≤A!e←AKeiS∃fA←L↓!e←OIC[fX1 bjt$~∀]¬∃∂∪≤AQ+%≤A=≤@E>λXDFDl~∀]
@~∃!K=aYJA¬eJAE∃G←[S9NAS]
eKCg%]OYr↓CoCe∀A←LAQQJAS5a←ei¬]GJA=LAOSYS]N@4∃G←]YS]GS9N~∃CIOk[K9ifAM=dAgk
PAG←9GKaiLACfAQQJAG=eeKGQ]Kgf↓←dAKEkSmC1K]GJ↓←LAaI←OeC5f\A)!KgJA¬eJ~∃	←iPAYKerA⊃SMMS
kYhA∃]iKeAeSgKL\A/J↓oSYXAgWKQGPAB↓ae←←_~∃←L↓BAgS5aYJAAe←aKIirA←_Aio↑↓ae←OIC[fA¬]HAY∃CmJA=iQKeLACfAAe←EY∃[fAM=dAiQ∀@~∃S9iKeKMiKHAIKCIKH\~∃⊃=nAI↑↓s←jA≥↑ACE=khAaI←mS]≤Aae←AKeiS∃fA←L↓ae←OIC[f}4∃∪\Ams←]gLQ bd@S|Ao∀A]←i∃HAGKIiCS\↓EK]K→SifA=LAIK→S]S]≤AgKiL~∃kg%]NAS9IkGi%mJAI∃MS]SQS←]f8@@A)!KeJA]CfAB↓]CikICXAo¬rA←L↓iQS]-S]NA¬E←kh4∃iQJ↓G←]gQekGi%←\A←_AC\A¬YO←e%iQZA=mKdAQQChAMKh\A]JAQCYJAKqAY←Si∃HAiQ¬h@~∃=EgKeYCiS←8AS\A=kd@AMikIr↓←LA→%' AaI←OeC5[S]N8A/JA9KKHAQ↑AeK
CYX~)iQJA=EgKeYCiS←8AiQCPAS]IUGiSm∀Agis1JAae=←Mf@!gKJ@∀e!%∀TA←\↓ws←\! bbr%|R@~)CeJAYCYSH↓M←e[LA←LAIKCg←9S]N~)←mKd↓gkGP↓I←[C%]f\AMS]GJ↓oJAS8AMCGPAIKM%]KHA=kdAI¬iBAgQekGiUeJAI=[CS]LAS\~)C\AS9IkGi%mJA[¬]]Kd0AShAMKK[f↓]CikICXAi<AY←←,AM←d↓S]Ik
iSmJ↓CeOk5K]if4∃oQK8Aae←YS]NAAe←aKIiSKf↓←LAaI←OeC5f\A)!SfASLAS]I∃KHAo!ChAo∀AI↑v↓oJAa∃eM←e4~∃S]⊃kGiS=\A←\↓iQJAMiekGQkeJA=LAiQ∀AKYK5K]if↓S\Ai!JAICQBAI←5CS\\4∀~∀~(]∂%∨U v~∃→←dAKaC[aY∀XAOSYK\~∀↓iQJA⊃KMS]%iS←\↓←L@JMCaaK9HJTA≥SmK\↓←\Awe←\Q HdS|A¬]HAi!JAIK→S]Si%←\~∃=L@JgIKmKeMJJTA≥SmK\↓←\Awe←\Q HfS|X~∀~∀9¬∂∪8A'→∃π(@fm)β¬∪PbPbn$w∂%∨U v~∀9¬∨1α4∃Caa∃]I7pms:@xtA7]k1Y7q:2ArvKKhJ(@2AG=]GCimMSegQ7q:w¬aaK]⊃7eKgQ7q:we;;:~(]!(b`~∃eKYKegKmq:@xu97]k1Y7q:2@P@$v~∃8KKhJ(@2ACAaK]ImeKmKIgK7e∃gi7qu:wG←9GCi7→Segimq:vPS;;:~∀]9λ~∀]	∨1∧~(]
 ~)oJAo%gPAi<AgQ←\AiQCPt~∀]	∨1α~)>JgCAaK]ImeKmKIgK7stweKm∃egK7a;:@z↓eKmKIgK7CAaK]Impws;tJTX~(]¬∨1λ~∀]
@~∃M←HAC]r↓YSgiLX@Jg`JTXA¬]H@JMrJT\↓)QJA%]IkGQS←\A]SYXA	JA←\↓iQJAMiekGQkeJA=L@Jg`JT\~(]β!βI(~∀]A(dh~(]¬∂%≤A)β	∪(fPTXb`XDjRv~(]∂%∨U ~∃8∀e¬Cg%fJTtJgpJ(ASf@∀fP@R∀T\~∃q/JA[UghAi!kfAg!←nt@∀gCaa∃]I7e∃mKeg∃7s:v @S:@tAeKm∃egK7¬aaK]⊃6P@Rms;:J(~∃9¬Uht@JMeKmKIgK7CAaK]IlP@Rwe;:@z↓eKmKIgK7stJT@A	rAiQ∀AIKL8A←L@∀gCaa∃]HJT8~∃9/∀A]←n↓KgiC	YSgP↓iQJAMie←]≥KdAe∃gkYhh@@Jg¬aaK]⊃7tvPS:@z↓tJT@Xβ∪\AQQJAM=YY←o%]NAaI←←L~)gKmKICXAS9iKe[∃ISCi∀AgiKAfAQCYJAEK∃\A←[%iiKH9>~∃9pJe¬CMSftJ(@Jgt∀TASfJfP@$JT\~)99'Q=n@Jg¬aaK]⊃6P@RlP@S:z@P@$JT\A∃Cgr\4∀~∃9pJe∪]⊃kGiS=\Agi∃`tJT↓βggk5JAiQ∀AYK[5BAM←HAYSgQfX@JMtJTX↓←LAY∃]OiP↓\v~∃q9!e←YJt@JMCaaK9I7G←9GCi7`wu:v @S:@tAG←]
Ci7pmu:JT8~∃99MS]GJJgG←9GCi68\]:J(ASfA9←h@JLP@RJ(XAiQ∃\ACaAYsS]≤AiQJ↓IKMS9SiS←8A←L@∀gCaa∃]HJT4∃99g¬sfAo∀A[kgPAae←YJt@JMG←]G¬i7pw¬aaK]⊃7tvPS;:@tAG←]
Ci7pmu:JT8~∃99	khA←UdAS]⊃kGiS=\AQsA←iQKMSfASLACaa1SGCE1JAgS9GJ@JMtJbA%fAgQ=eiKd↓iQC\~∃98∀gG←]
Ci7pmu:Jb8~∃99=kdAe∃gkYh↓M←YY=of\~)9'↑AQQJA¬¬gSfA→←dA←UdA[C%\AeKMkYhA%fAKgQCEYSMQKH\4∀]β!¬%(~∀9∂%∨+@~∃8JI∪]Ik
iS←\↓giK`hJTAβMgk[J↓iQJAIKgkYPAM←d↓YSgiLX@JghJTXA=LAYK9OiPA8v~∃9Ae←mJh~∃8PDR@@JMCaaK9I7eKYKegKms:we∃mKeg∃7G←]
Ci7pmu;;:zAeKYKegKmCaaK9I7G←9GCi7`wu:we;:JT4∃8AβAaYsS9NAiQ∀AIKM%]SiS=\A←LJgeKYKegJ∀TAi↑↓iQJA1⊃&A←_@PbR↓sSKY⊃ft~∀9!(d~)9>@@PdR@@JgCAaK]ImeKmKIgK7stwCaa∃]I7e∃mKeg∃7u:w
←]GCQ7pvPS;;:∀T\~∀9!(d~)8AβaAYsS]≤AiQJ↓IKMS9SiS←8A←L@∀gCaa∃]HJT↓i↑Ai!JA%⊃LA←L@ bRAs%KYIfh~∀]!Pd~∃9|@@@PLR@@@∀geKm∃egK7
←]GCQ7pwCAaK]Imtws;u:\JT4∀]!(H~∃8A¬aaYs%]NAi!JAIK→S]Si%←\A←_@Jge∃mKeg∀JTAi<@PfR↓sSKY⊃ft~∀9!(d~)9>@@PhR@@JgCAaK]Ireverse[append[z;y]];concat[x;( )]].%*
.PT2
\ Using our induction hypothesis on (4) gives:
.PT2
\←   (5)   %3append[append[reverse[y];reverse[z]];concat[x;( )]]%*
.PT2
\ At this point we must establish that    (2) = (5).
\ But this is just an instance of the associativity of %3append%*:
\←%3append[x;append[y;z]] = append[append[x;y];z].%*  
.END

The structure of the proof is analogous to proofs by mathematical 
induction in elementary number theory. The ability to perform such proofs
is a direct consequence of our careful definition of data structures.
Examination of the proof will show that there is a close relationship
between what we are inducting on in the proof and what  we are recurring on
during the evaluation of the  expressions. A program
written by Boyer and Moore has been reasonably successful in generating
proofs like the above by exploiting this relationship. 
⊗↑[Boy#75]↑,#⊗↑[Moor#75b]↑⊗↓There is also a formal system 
 based on a typed %9λ%1-calculus
which has had significant success in proving properies of programs. 
⊗↑[LCF#72]↑,#⊗↑[New#75]↑.
More recently ⊗↑[Car#76]↑ has developed a  formal system including
rules of inference, a proof checker, and a viable programming language
which is based on a "typed LISP".←.


.CENT(Problems)

1.##Prove the associativity of %3append%*.
.NL
2.##Analysis of the above proof shows frequent use of other results for LISP
functions. Fill in the details. Investigate the possibility of formalizing
this proof, showing what axioms are needed.
.NL
3.##Show the equivalence of %3fact%* ({yon(P20)}) and %3fact%41%1 ({yon(P21)}).
.NL
4.##Show the equivalence of %3length%* and %3length%41%1 ({yon(P19)}).
.NL
5.##Using the definition of %3reverse%*, given on {yon(P16)}, prove:
.BOXA
←%3reverse[reverse[x]] = x%*.

.END